Partition s into as many parts as possible so that each letter appears in at most one part. Return the sizes of the parts.
Before you code
Each letter spans an interval from its first to its last occurrence. A piece can only end where no letter seen so far continues past it.
Hints
- Record the last index of each letter.
- Walk the string, extending
end = max(end, last[ch]). - When
i == end, close the piece and start a new one.
Production & complexity notes
When solving Partition labels on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Scheduling and intervals to reinforce the underlying pattern.
What it practices
Greedy reasoning on intervals, from Scheduling and intervals.