Partition Labels
Medium · Intervals · String · Hash Table · Greedy · Two Pointers
Problem
You are given a string s. Cut it into as many contiguous parts as possible so that every letter appears in at most one part. Joined back together in order, the parts must give s again.
Return the list of part sizes, in order.
Examples
Input: s = "abacdcef" Output: [3,3,1,1]
The a's force 'aba' into one part and the c's force 'cdc'; 'e' and 'f' stand alone.
Input: s = "xyzx" Output: [4]
The two x's sit at both ends, so the whole string is one part.
Input: s = "aabb" Output: [2,2]
The a's and the b's can be separated.
Constraints
- 1 <= len(s) <= 500
- s consists of lowercase English letters.
Approaches
- Baseline: grow each part until no letter crosses the cut — time O(n²), space O(n)
Follow-up
Each letter covers the interval from its first to its last index, and the parts are those intervals merged: this is Merge Intervals in disguise. The use cases cut an array the same way: a permutation into sortable chunks, and a single cut with everything on the left at most everything on the right.
Related problems
Start free on Cariara · Coding problems · System design studio
