495. Partition Labels
You receive a string s of lowercase English letters. Cut it into contiguous pieces so that no letter shows up in two different pieces — every letter of the alphabet must be confined to at most one piece. Gluing the pieces back together in order must reproduce s exactly.
Among all ways to do this, make as many pieces as possible (that partition is unique), and return the list of piece lengths, left to right.
For example, "abacdc" splits into "aba" + "cdc" — a and b live only in the first piece, c and d only in the second — and no finer split is possible, so the answer is [3, 3].
Example 1:
Input: s = "ababcbacadefegdehijhklij"
Output: [9, 7, 8]
Explanation: The finest valid cut is "ababcbaca" + "defegde" + "hijhklij". Every occurrence of a, b, c falls in piece 1; d, e, f, g in piece 2; h, i, j, k, l in piece 3. Cutting any piece further would strand a letter on both sides.
Example 2:
Input: s = "eccbbbbdec"
Output: [10]
Explanation: The letter e appears at index 0 and again at index 8, and c stretches to index 9, chaining the whole string into one unbreakable piece.
Constraints:
- 1 ≤ s.length ≤ 500
- s consists of lowercase English letters only.
Hints:
A piece that contains some letter must contain ALL occurrences of that letter — so a piece starting at i must reach at least to the last occurrence of every letter inside it.
Precompute each letter's last index. Sweep with a growing boundary: end = max(end, last[s[j]]). The moment j catches up to end, nothing inside points further right — cut there, greedily giving the shortest (and thus most) pieces.
Two pointers carry the whole state: start of the current piece and the farthest last-occurrence seen. When j == end, append end - start + 1 and restart at j + 1.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "ababcbacadefegdehijhklij"
Expected output: [9, 7, 8]