aboutsummaryrefslogtreecommitdiff
path: root/partition_labels.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-29 18:43:38 -0600
committerJack Sangdahl <[email protected]>2025-03-29 18:43:38 -0600
commite98eec899e88073264dff288b0778f9e675ecb2e (patch)
treeb4fa1f93c75fcae9ce6a9b66f58d6793e8fc1103 /partition_labels.py
parent4dee4d8757675b9cb1ee32e2046b844056d27961 (diff)
downloadleetcode-e98eec899e88073264dff288b0778f9e675ecb2e.tar.gz
leetcode-e98eec899e88073264dff288b0778f9e675ecb2e.zip
763. partition labels
Diffstat (limited to 'partition_labels.py')
-rw-r--r--partition_labels.py34
1 files changed, 34 insertions, 0 deletions
diff --git a/partition_labels.py b/partition_labels.py
new file mode 100644
index 0000000..13556c5
--- /dev/null
+++ b/partition_labels.py
@@ -0,0 +1,34 @@
+# 763. Partition Labels
+
+"""
+you are given a string 's'. we want to partition the string into as many
+parts as possible so that each letter appears in at most one part. for
+example, the string 'ababcc' can be partitioned into '["abab", "cc"]'. note
+that the partition is done so that after concatenating all the parts in
+order, the resultant string should be 's'. return a list of integers
+representing the size of these parts.
+"""
+
+
+class Solution(object):
+ def partitionLabels(self, s):
+ """
+ :type s: str
+ :rtype: List[int]
+ """
+ curr, ans = 0, [0]
+ ends = {c: i for i, c in enumerate(s)}
+ while curr < len(s):
+ prev = ends[s[curr]]
+ while curr <= prev:
+ sym = s[curr]
+ prev = max(prev, ends[sym])
+ curr += 1
+ ans.append(curr)
+ return [ans[i] - ans[i - 1] for i in range(1, len(ans))]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.partitionLabels(s="ababcbacadefegdehijhklij"))
+ print(obj.partitionLabels(s="eccbbbbdec"))