Partition Labels
On this page
Problem statement
Split a string of lowercase letters into as many pieces as possible so that every letter appears in at most one piece. Return the sizes of the pieces in order. Joining the pieces must give back the original string.
It is a compact greedy question that is really an intervals question in disguise: each letter covers the span from its first to its last occurrence. Original problem: LeetCode 763.
Example

Input: "abcadefgdhij"
Output: [4, 5, 1, 1, 1] # "abca" | "defgd" | "h" | "i" | "j"
Input: "zz"
Output: [2]
Input: "xyz"
Output: [1, 1, 1]
Constraints (assumed)
- 1 ≤ length ≤ 500.
- Lowercase English letters only.
What this question tests
- Turning "each letter in one piece" into "each piece must reach its letters' last occurrences".
- A greedy cut, and an argument for why cutting as early as possible gives the most pieces.
- Seeing the link to merging intervals.
Questions to ask first
- Return the sizes or the pieces themselves? (Here: sizes.)
- Only lowercase letters? Decides between a 26-slot array and a hash map.
- Must the pieces keep the original order? (Yes; we only cut, never reorder.)
- Empty string? Return an empty list.
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.