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. Return a list of integers representing the size of these parts.
Example 1: Input: s = “ababcbacadefegdehijhklij” Output: [9,7,8] Explanation: The partition is “ababcbaca”, “defegde”, “hijhklij”. This is a partition so that each letter appears in at most one part. A partition like “ababcbacadefegde”, “hijhklij” is incorrect, because it splits s into less parts. Example 2: Input: s = “eccbbbbdec” Output: [10]
- code
class Solution:
def partitionLabels(self, s: str) -> List[int]:
res = []
i = 0
while i < len(s):
start = i
end = s.rfind(s[start])
index_between = start + 1
while index_between < end:
curend = s.rfind(s[index_between])
if curend > end:
end = curend
index_between += 1
res.append(end - start + 1)
i = end + 1
return res
- code
class Solution:
def partitionLabels(self, s: str) -> List[int]:
res = []
cur_left = 0
visited = set()
while s:
visited.add(s[0])
cur_right = s.rfind(s[0])
cur_chars = set(list(s[cur_left:cur_right+1]))
while cur_chars:
c = cur_chars.pop()
if c not in visited:
visited.add(c)
new_right = s.rfind(c)
if new_right > cur_right:
cur_chars.update(set(list(s[cur_right+1:new_right+1])))
cur_right = new_right
res.append(cur_right - cur_left + 1)
s = s[cur_right+1:]
return res
- code
class Solution(object):
def partitionLabels(self, S):
last = {c: i for i, c in enumerate(S)}
start = end = 0
ans = []
for i, c in enumerate(S):
end = max(end, last[c])
if i == end:
ans.append(i - start + 1)
start = i + 1
return ans