DSA problem
Partition Labels
You are given a string s. You 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 each part. The concatenation of the parts in order must equal s.
The constraint forces every part to contain all occurrences of every letter it includes. The problem is naturally an interval problem: each distinct letter c is associated with the closed interval [firstIndex(c), lastIndex(c)] inside s. A valid partition is a set of disjoint super-intervals that each fully contain the intervals of all the letters inside them.
The greedy algorithm rests on a single precomputation: for each letter, find the index of its last occurrence in s. Then iterate left to right, maintaining a "current segment" that initially ends at the last occurrence of s[0]. As you scan forward, every new character may push the segment's end further right (whenever its last occurrence is bigger).
The moment your scan index equals the current segment end, you are guaranteed every letter inside the segment has been fully consumed (its last index has been visited), and no letter in the segment appears later in the string. That moment marks a partition boundary: record the length and start a new segment. The algorithm runs in O(n) time and O(1) auxiliary space (26-letter map).
Examples
s = "ababcbacadefegdehijhklij"[9,7,8]s = "eccbbbbdec"[10]s = "abc"[1,1,1]Constraints
- 1 <= s.length <= 500
- s consists of lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.