Given a string s, split it into as many pieces as possible so that each letter appears in at most one piece. Joining the pieces in order must give back s. Return a list with the length of each piece, in order.
- 1 <= s.length <= 500
- `s` has only lowercase English letters
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A brute force tries every cut position and checks if the letters on each side are disjoint, which is O(n^2) or more. Instead, first store last[c], the final index of each letter. Start a piece at index start and keep end, the farthest last index of any letter seen in this piece. When the scan reaches i == end, every letter in the piece has finished, so we can cut. The greedy is safe because cutting at the earliest possible point never forces a later piece to be shorter, so it gives the most pieces.
Algorithm
- Fill
last[c]with the last index of each letter. - Set
start = 0,end = 0. - For each index
i:end = max(end, last[s[i]]). - If
i == end, appendend - start + 1and setstart = i + 1. Return the list.
O(n)Space: O(1), only 26 lettersstart and end give them.class Solution: def partitionLabels(self, s: str) -> List[int]: last = {c: i for i, c in enumerate(s)} # last index of each letter res = [] start = end = 0 for i, c in enumerate(s): end = max(end, last[c]) # piece must reach here if i == end: # every letter so far is done res.append(end - start + 1) start = i + 1 return res