MediumHash TableTwo PointersStringGreedy

Partition Labels

1 approach, code in every language

You are given a string made up of lowercase English letters. Your job is to break it into the largest possible number of contiguous pieces so that every letter ends up in exactly one piece. In other words, no letter may appear in two different pieces.

When the pieces are concatenated back together in order they must reproduce the original string. Return a list containing the length of each piece, in left-to-right order.

Example 1

Input: s = "ababcbacadefegdehijhklij"

Output: [9,7,8]

The split is "ababcbaca", "defegde", "hijhklij". Every distinct letter is confined to a single piece, and using fewer cuts would force some letter to straddle a boundary.

Example 2

Input: s = "eccbbbbdec"

Output: [10]

Both 'e' and 'c' reappear near the end, so the last occurrence of the earliest letters reaches the end of the string. The whole string must stay as one piece.

Constraints

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

Greedy with Last-Occurrence Index

Precompute each character's final position, then extend the current piece until the scan pointer catches the farthest required end.

Loading animation…

Intuition

A piece is only valid once it contains the last occurrence of every letter it holds. So the earliest we can possibly cut after position i is the maximum last-index among all characters seen so far. We walk left to right, continually pushing the candidate boundary outward to that maximum. The moment our scan index equals the boundary, nothing to the left needs anything to the right, so we can safely cut. Recording the width of each cut piece and restarting gives the greedy optimum, which also happens to be the largest number of pieces.

Algorithm walkthrough

1Scan the string once and store, for every character, the index of its last appearance.
2Initialize a partition start pointer and a running end pointer to 0.
3For each index i, update the end pointer to the max of itself and the last index of s[i].
4If i now equals the end pointer, the current window is self-contained: append (end - start + 1) to the answer.
5Move the start pointer to i + 1 and continue scanning until the string is exhausted.
6Return the collected list of piece lengths.

Implementation

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

Time

O(n)

Space

O(1)

One pass to record last indices and one pass to cut. The character map holds at most 26 entries, so extra space is constant.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Duty Roster Blocks is our own problem on the technique behind Partition Labels: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free