# 763. Partition Labels
A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.
Example:
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.
# Solution
Approach 1: build an index of first and last occurence of all characters.
# Code (Python)
Approach 1:
def partitionLabels(self, S: str) -> List[int]:
# idea: like merge intervals, but first need to build a map of "intervals" for each letter
intervals = {}
for i, letter in enumerate(S):
if letter not in intervals:
intervals[letter] = [i, i]
else:
intervals[letter][-1] = i
chunks = []
for interval in sorted(intervals.values()):
if not chunks or interval[0] > chunks[-1][1]:
chunks.append(interval)
else:
chunks[-1][1] = max(chunks[-1][1], interval[1])
return [chunk[1] - chunk[0] + 1 for chunk in chunks]
# Code (C++)
Approach 1:
Approach 2: