Problem statement

Partition the string s into as many parts as possible so that no letter appears in more than one part (concatenating the parts in order must reproduce s).

Return a list of the sizes of these parts.

Example 1

Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation: Parts: "ababcbaca", "defegde", "hijhklij".

Example 2

Input: s = "eccbbbbdec"
Output: [10]

Constraints

• 1 <= s.length <= 40
• Lowercase English letters.

Hints for Partition Labels

1. Hint 1

   Record the last index of every letter.

2. Hint 2

   Extend the current part's end to the last occurrence of each letter you meet; cut when i reaches it.

How to solve Partition Labels

A part can only end where every letter inside it has finished for good. So precompute the last index of each letter, then sweep: the current part must stretch at least to the last occurrence of every letter met so far. The moment the walking index catches up with that frontier, the part is closed.

Approach

1. Record the last index at which each letter appears.
2. Track start (where the current part began) and end (how far it must stretch).
3. For each index i, extend end = max(end, last[s[i]]).
4. When i == end, no letter inside can appear later — cut here, record the length end - start + 1, and set start = i + 1.
5. The recorded lengths are the answer.

Why it works

Cutting at the earliest legal point is what maximises the number of parts. The invariant is that end is the smallest index at which the current part could legally close, given the letters seen so far; closing any earlier would strand a letter across two parts. Since every cut is taken as early as the constraints permit, no alternative partition can produce more parts — and the greedy choice never blocks a later one, because the remaining suffix is an independent instance of the same problem.

Complexity

• Time — O(n)
• Space — O(1) — the table holds at most 26 letters

Pitfalls

• end must be a running maximum, not just the last occurrence of the current character.
• The part length is end - start + 1; forgetting the +1 yields lengths one short.
• Reset start to i + 1 right after a cut.
• Build the last-occurrence table in a separate first pass — you cannot know a letter's final position while still scanning.

Reference solution

Python

from typing import List

def partitionLabels(s: str) -> List[int]:
    last = {ch: i for i, ch in enumerate(s)}
    out = []
    start = 0
    end = 0
    for i, ch in enumerate(s):
        end = max(end, last[ch])
        if i == end:
            out.append(end - start + 1)
            start = i + 1
    return out

Java

public static int[] partitionLabels(String s) {
    int[] last = new int[128];
    for (int i = 0; i < s.length(); i++) last[s.charAt(i)] = i;
    List<Integer> parts = new ArrayList<>();
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        if (last[s.charAt(i)] > end) end = last[s.charAt(i)];
        if (i == end) {
            parts.add(end - start + 1);
            start = i + 1;
        }
    }
    int[] out = new int[parts.size()];
    for (int i = 0; i < parts.size(); i++) out[i] = parts.get(i);
    return out;
}

C++

vector<int> partitionLabels(string s) {
    int last[128];
    for (int i = 0; i < 128; i++) last[i] = -1;
    for (int i = 0; i < (int) s.size(); i++) last[(int) s[i]] = i;
    vector<int> out;
    int start = 0, end = 0;
    for (int i = 0; i < (int) s.size(); i++) {
        if (last[(int) s[i]] > end) end = last[(int) s[i]];
        if (i == end) {
            out.push_back(end - start + 1);
            start = i + 1;
        }
    }
    return out;
}

JavaScript

var partitionLabels = function(s) {
    const last = new Map();
    for (let i = 0; i < s.length; i++) last.set(s[i], i);
    const out = [];
    let start = 0, end = 0;
    for (let i = 0; i < s.length; i++) {
        end = Math.max(end, last.get(s[i]));
        if (i === end) {
            out.push(end - start + 1);
            start = i + 1;
        }
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design a Food Rating System Medium
• Design Bitset Medium
• Iterator for Combination Medium
• Time Based Key-Value Store Medium
• Map Sum Pairs Medium
• Implement Magic Dictionary Medium