Partition Labels

MediumGreedyNeetCode 150MidOpen on LeetCodeUpdated Sep 21, 2026

You're given a string s of lowercase letters. Split it into as many contiguous parts as possible so that each letter appears in at most one part: for example, every 'a' in s must end up in the same part. Read in order, the parts must join back into s. Return a list of the parts' lengths, from left to right.

Examples

s = "ababcbacadefegdehijhklij" returns [9,7,8]

The parts are "ababcbaca", "defegde" and "hijhklij". The last a sits at index 8 and every b and c comes before it, so the first part must run through index 8 and can stop there. No letter appears in two parts.

s = "eccbbbbdec" returns [10]

The e at index 0 appears again at index 8, and the c at index 1 appears again at index 9, the very end. No cut is possible, so the whole string is one part.

s = "abaccbdeed" returns [6,4]

first part

The b's at indices 1 and 5 force the first part to run through index 5.

The parts are "abaccb" and "deed". The first part can't end at index 2 after the last a, because the b at index 1 comes back at index 5.

Constraints

1 <= s.length <= 500
s consists of lowercase English letters.

Hints

Hint 1

A part can't end until every letter inside it has appeared for the last time. Where does each letter appear last?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Record the last index of every letter in one pass. Then sweep left to right, keeping end as the farthest last occurrence of any letter seen in the current part. When i reaches end, every letter in the part has finished, so this is the earliest safe cut; record its size and start the next part at i + 1. Cutting at the earliest safe point is what maximizes the number of parts. Extra space is O(1) because there are only 26 letters.

Time

O(n)

Space

O(1)

Pitfall

Cutting when you reach the current letter's own last occurrence is wrong; end must be the max last index over every letter seen so far in the part. Also return sizes (end - start + 1), not end indices.

Solutions

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] last = new int[26];
        for (int i = 0; i < s.length(); i++) {
            last[s.charAt(i) - 'a'] = i;
        }

        List<Integer> sizes = new ArrayList<>();
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, last[s.charAt(i) - 'a']);
            if (i == end) {
                sizes.add(end - start + 1);
                start = i + 1;
            }
        }
        return sizes;
    }
}

from typing import List

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