Partition Labels

Problem

You are given a string s of lowercase letters. Cut it into as many contiguous pieces as possible such that no letter appears in more than one piece. Return the list of piece lengths, in order from left to right.

• s has between 1 and 20,000 characters, all lowercase English letters.
• The pieces, concatenated in order, must reproduce s exactly.

Examples

• s = "gtgbgsbahahjjkfkflf" → [7, 4, 2, 6]. Pieces "gtgbgsb", "ahah", "jj", "kfkflf"; every letter lives entirely in one piece, and no finer cut works.
• s = "zaaza" → [5]. The letter z sits at both ends, so the string cannot be cut at all.
• s = "xyz" → [1, 1, 1]. All letters distinct: each is its own piece.

Hints

1. If a piece contains the first a, it must also contain the last a. What does that tell you about where the piece must end?
2. As you scan, keep track of the furthest position the current piece is obliged to reach. When is it safe to cut?
3. Precompute each letter's last index; sweep left to right maintaining end = max(end, last[ch]), and cut when i == end.