Partition Labels

Partition Labels is a greedy with one running value: the end of the current piece. Every letter you meet may push that end further right. When the index you are on is the end, nothing inside the piece reaches beyond it, and you can cut.

It is also a quiet cousin of the Intervals section. Each letter spans an interval from its first to its last position, and the pieces are those intervals merged. The greedy version just never builds the intervals.

The problem

Given a string of lowercase letters, cut it into as many contiguous pieces as possible such that each letter appears in at most one piece. Return the lengths of the pieces, left to right. Joining the pieces must give back the original string.

• "abacbdefe" → [5, 1, 3]. The pieces are abacb, d, efe. You cannot cut inside abacb: a appears at 0 and 2, b at 1 and 4.
• "caddcbeffge" → [5, 1, 5]: caddc, b, effge.

Constraints: 1 ≤ length ≤ 10⁵, lowercase English letters only.

Clarifying questions

• Only lowercase letters? Yes — so at most 26 distinct letters. The code works for any characters anyway.
• Lengths or the pieces themselves? Lengths.
• Must pieces be contiguous? Yes, they are cuts of the string, not groups of letters.

Approach 1: the simple way

Walk the string. After each index i, you may cut if no letter in the current piece appears again after i. Check that with two sets.

1def partition_labels_brute(s: str) -> list[int]:2    """Cut after i when no letter seen in the piece appears again later."""3    sizes = []4    start = 05    for i in range(len(s)):6        if not set(s[start:i + 1]) & set(s[i + 1:]):7            sizes.append(i - start + 1)8            start = i + 19    return sizes

Cutting as soon as it is allowed is already the greedy rule — it is correct. The problem is cost. Each check builds two sets over up to n characters, so the whole thing is O(n²) time and O(n) space. For 10⁵ characters that is 10¹⁰ character reads. The check keeps asking the same question — "does any letter here appear later?" — and recomputes the answer from scratch.

The key insight

"Does letter c appear later?" has a precomputable answer: the last index where c appears. Store it once for every letter.

Now think about the current piece. If it contains c, it must reach at least last[c]. So the piece must end at the maximum last[...] of every letter inside it. Walk left to right, keep that maximum as end, and each new letter can only push end further right. When i == end, every letter in the piece has its last occurrence at or before i. Cut.

Why cutting at the first possible moment gives the most pieces: a cut is only allowed where no letter crosses it. Cutting early never removes a later option — every cut you could have made later is still available in the rest of the string. That is the exchange argument in one sentence.

Approach 2: optimised — stretch to the last occurrence

1def partition_labels(s: str) -> list[int]:2    """Stretch each piece to the last occurrence of every letter inside it."""3    last = {ch: i for i, ch in enumerate(s)}   # later indices overwrite earlier ones4    sizes = []5    start = end = 06    for i, ch in enumerate(s):7        end = max(end, last[ch])      # the piece must reach at least here8        if i == end:                  # nothing inside reaches further: cut9            sizes.append(end - start + 1)10            start = i + 111    return sizes

1. Build last in one pass; the dictionary comprehension keeps the final index for each letter.
2. For each character, stretch end to cover its last occurrence.
3. When i catches up with end, record the piece and start a new one at i + 1.

Dry run on "abacbdefe" (last positions: a → 2, b → 4, c → 3, d → 5, e → 8, f → 7):

Result [5, 1, 3]. The lengths add up to 9, the length of the string — a quick check you can do out loud.

Complexity: O(n) time — two passes. O(1) extra space for lowercase letters, since last holds at most 26 entries (O(k) for an alphabet of size k). The output list is not counted.

Edge cases

• One character, "a" → [1].
• All the same letter, "zz" → [2]: one piece; z spans the whole string.
• All distinct, "abc" → [1, 1, 1]: every index is its own last occurrence.
• First letter appears last, "abca" → [4]: a forces the first piece to cover everything.

Follow-ups

• Return the pieces instead of the lengths? Append s[start:end + 1] instead of the length.
• Solve it as intervals? Build [first, last] for each letter, sort by start and merge overlaps; the merged intervals are the pieces. It is O(n + k log k) and a good way to show you see the connection.
• Pieces must also have no repeated letters inside? Different problem: that is a sliding window or a simple scan that cuts whenever a letter repeats.