Partition Labels

Problem

You are given a string s of lowercase English letters. Partition s into as many contiguous, non-overlapping parts as possible so that each letter appears in at most one part (every occurrence of any given letter must lie inside a single part). The parts, concatenated in order, must reproduce s.

Return a list of the sizes of these parts, in left-to-right order.

Examples

• s = "ababcbacadefegdehijhklij" → [9, 7, 8] — parts "ababcbaca", "defegde", "hijhklij"; e.g. every a is inside the first part, every d/e inside the second.
• s = "eccbbbbdec" → [10] — e first appears at index 0 and last at index 8, forcing the whole string into one part.
• s = "abcdef" → [1, 1, 1, 1, 1, 1] — every letter is unique, so each character is its own part.

Constraints

• 1 <= len(s) <= 500
• s consists of lowercase English letters only ('a'–'z').
• The input is small, but the intended solution is an O(n) two-pass scan.

Think about it first

TL;DR

Record each letter’s last index, then sweep left to right cutting a part as soon as the scan reaches the farthest last-index seen — greedy, O(n) time, O(1) space (26 letters).

Approach 1 — Brute force (grow each part, verify no letter leaks out)

Start a part at the current position and keep extending it one character at a time; after each extension, check whether every letter inside the part fails to appear anywhere later in the string. Cut at the first length that passes, then repeat from the next index.

from typing import List


def partitionLabels(s: str) -> List[int]:
    n = len(s)
    res = []
    i = 0
    while i < n:
        j = i
        while True:
            part = set(s[i:j + 1])
            # does any letter in the part appear after index j?
            if any(c in part for c in s[j + 1:]):
                j += 1            # letter leaks out; extend
            else:
                break
        res.append(j - i + 1)
        i = j + 1
    return res

Complexity: O(n^2) time (each extension re-scans the tail), O(n) space. Correct, but it repeatedly rescans the suffix instead of precomputing where letters end.

Approach 2 — Greedy (last-occurrence, cut at the first legal boundary)

Precompute last[c] = the final index where letter c occurs. A part that begins at index i must extend at least to last[s[i]], and as it grows it must also cover the last occurrence of every other letter it includes. So the smallest legal end for the part is the running maximum of last[c] over the letters seen since the part began.

Greedy-choice property (why cutting early is globally optimal). When the scan index equals the running end, every letter currently inside the part has all its occurrences at or before end, so cutting here produces a valid part. It is also the shortest valid part starting at this position, since any earlier cut would leave a letter’s later occurrence outside the part. Choosing the shortest valid first part maximizes the total count: the shortest first part is a prefix of any longer legal first part, so it leaves a superset suffix that offers at least as many further cut points. This is a prefix / exchange argument — replacing the first part of any optimal solution with the greedy (shortest legal) first part never reduces the number of parts. Induct on the suffix.

from typing import List


def partitionLabels(s: str) -> List[int]:
    last = {c: i for i, c in enumerate(s)}   # last index of each letter

    res = []
    start = 0
    end = 0
    for i, c in enumerate(s):
        end = max(end, last[c])              # part must reach this far
        if i == end:                         # first legal boundary
            res.append(i - start + 1)
            start = i + 1
    return res

Walkthrough with s = "ababcbacadefegdehijhklij":

• last includes a:8, b:5, c:7, d:14, e:15, f:11, g:13, h:19, i:22, j:23, k:20, l:21.
• Scanning: at i=0 (a) end = 8; the running max stays 8 through indices 1–7 (b,a,b,c,b,a,c all end ≤ 8); at i=8 (a) i == end == 8 → cut → part length 9, start = 9.
• From i=9 (d) end = 14; e→15, so end = 15; reach i=15 → cut → length 15 - 9 + 1 = 7, start = 16.
• From i=16 (h) end = 19; i→22, j→23 push end = 23; reach i=23 → cut → length 23 - 16 + 1 = 8.

Result: [9, 7, 8].

Complexity: O(n) time (one pass to build last, one pass to cut), O(1) space (last holds at most 26 entries).

Common pitfalls

• Off-by-one in the length: the part is [start, i] inclusive, so its size is i - start + 1, not i - start.
• Resetting end to 0 (or forgetting to advance start) after a cut — start must jump to i + 1, and end naturally gets refreshed by the next character.
• Overwriting last[c] incorrectly: the dict comprehension {c: i for i, c in enumerate(s)} keeps the last i per letter, which is exactly what we want.
• Cutting at a letter’s first repeat instead of tracking the running-max last index — that misses letters introduced mid-part.

Pattern takeaway

When each part is constrained so that everything starting inside must also finish inside, precompute each element’s last position, then sweep while extending the current part to the running-max last position and cut at the first index where nothing inside reaches further. Taking the shortest legal prefix maximizes the number of parts, the same logic behind interval partitioning: the smallest valid commitment leaves the most room for later cuts.