Partition Labels
Medium · rating 1550 · Greedy, Strings, Hashing
Read a string of lowercase letters. Partition it into as many contiguous pieces as possible so that each letter appears in at most one piece. Print the sizes of the pieces in order, space-separated.
For ababcbacadefegdehijhklij print 9 7 8.
Constraints: 1 ≤ length ≤ 105
Editorial
Approach
Record the last index at which each letter appears. Sweep left to right, extending the current piece's end to the farthest last-occurrence of any letter seen so far. When the scan position reaches that end, every letter inside is fully contained, so close the piece.
last = {c: i for i, c in enumerate(s)}
start = end = 0
for i, c in enumerate(s):
end = max(end, last[c])
if i == end: sizes.append(i - start + 1); start = i + 1Complexity
Time: O(n). Space: O(1) (fixed alphabet).
Related problems
- Longest Substring Without Repeats — Medium
- Count Anagram Groups — Medium
- Sort by Frequency — Medium
- Keypad Taps — Medium
- Election Winner — Medium
- First Unique Character — Medium