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').
• Small input, but the intended solution is a clean O(n) two-pass — no need for anything heavier.

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


class Solution:
    def partitionLabels(self, 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)

The insight: precompute last[c] = the final index where letter c occurs. A part that begins at index i is legal only if it extends at least to last[s[i]]; and as it grows it must also cover the last occurrence of every other letter it swallows. So the smallest legal part ending 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, and it is the shortest valid part starting at this position (any earlier cut would strand a letter’s later occurrence outside the part). Choosing the shortest valid first part is optimal for maximizing the count of parts: whatever partition of the remaining suffix is achievable after a longer first cut is also achievable after the shortest cut, because the shortest first part is a prefix of any longer legal first part, leaving a superset suffix that offers at least as many further cut points. Formally 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


class Solution:
    def partitionLabels(self, 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.
• Trying to be clever and cut 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 by “everything that starts 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. Greedily taking the shortest legal prefix maximizes the number of parts — the same “smallest valid commitment leaves the most room” logic behind interval partitioning.