763. Partition LabelsMedium

Partition Labels

MediumTwo PointersHash TableGreedyString·AmazonGoogle

You are given a string s consisting of lowercase English letters. We want to split the string into as many substrings as possible, while ensuring that each letter appears in at most one substring.

Return a list of integers representing the size of these substrings in the order they appear in the string.

Example 1:

Input:s = "xyxxyzbzbbisl"

Output:[5, 5, 1, 1, 1]

Split into "xyxxy", "zbzbb", "i", "s", "l". No character appears in more than one part.

Example 2:

Input:s = "abcabc"

Output:[6]

Every character appears multiple times throughout — the whole string is one partition.

Constraints:

1 ≤ s.length ≤ 500
s consists of lowercase English letters only.

💡

Intuition

The key insight: for any character, all of its occurrences must live in the same partition.That means if you've included one 'a', you must include every 'a'.

So as you scan left-to-right, for each character you see, your current partition must extend at least to that character's last occurrence in the string. Once your scan pointer reaches the current partition's end boundary — you're done with that partition.

Mental model

Think of each character as a rubber band stretched to its last occurrence. Your current partition is the union of all rubber bands of characters you've included so far. When your pointer catches up to the rightmost stretch — that partition snaps closed.

Walk-through on "xyxxyzbzbbisl":

1Precompute last index: x→3, y→4, z→7, b→9, i→10, s→11, l→12
2i=0 'x': end = max(0, 3) = 3
3i=1 'y': end = max(3, 4) = 4
4i=2,3 'x': end stays 4
5i=4 'y': end stays 4 → i == end → cut! size=5
6i=5 'z': end = max(5, 7) = 7 … i=9 'b': end stays 9 → i == end → cut! size=5
7i=10 'i': end=10 → cut (size=1). Same for 's' and 'l'.

📚

Prerequisites

→Hash Maps — store and quickly look up the last occurrence index of each character.
→Greedy Algorithms — make the locally optimal choice (extend partition to the farthest last occurrence) to achieve the global optimum.
→Two Pointers / Sliding Window — track the current scan position and partition end boundary.

Approach 1 — Brute Force

O(n²) Time

✂️

Check Every Possible Cut

Time O(n²)Space O(n)

For every possible cut position, check whether any character in the left segment also appears in the right segment. If none do, the cut is valid.

Why it's not optimal: For each boundary we scan remaining characters — O(n²). Precomputing last occurrences lets us cut in a single O(n) pass.

def partitionLabels(s):
    res, start = [], 0
    while start < len(s):
        end = start
        for j in range(start, len(s)):
            # extend end to last occurrence of s[j]
            end = max(end, s.rfind(s[j]))
            if j == end: break
        res.append(end - start + 1)
        start = end + 1
    return res

Approach 2 — Two Pointers + Greedy (Optimal)

O(n) Time · O(1) Space

🏷️

Extend Partition to Last Occurrence of Each Character

Time O(n)Space O(1)

Two passes: first record each character's last index. Then scan left-to-right, extending end to cover the last occurrence of every character seen so far. When i == end, the partition is complete.

1Build last[c] = last index of character c in s.
2Initialize start = end = 0.
3For each i: update end = max(end, last[s[i]]).
4When i == end: record size end - start + 1, set start = i + 1.

READYPress ▶ or step forward to begin.

✓

—

Executing Code

def partitionLabels(s):

    # Pass 1: last occurrence of each char

    last = {}  

    for i, c in enumerate(s):

        last[c] = i

    # Pass 2: greedy scan

    res, start, end = [], 0, 0

    for i, c in enumerate(s):

        end = max(end, last[c])

        if i == end:

            res.append(end - start + 1)

            start = i + 1

    return res

⚠ Common Pitfalls

!
Not precomputing last indices — trying to find the last occurrence on the fly during the main scan leads to O(n²). Always do a first pass to build the map.
!
Forgetting to reset start — after recording a partition, set start = i + 1. Omitting this causes sizes to accumulate incorrectly.
!
Off-by-one in boundary check — the partition ends exactly when i == end, not i >= end.

📊

Complexity Analysis

Time — O(n)

Two linear passes over the string: one to build the last-occurrence map, one to find partition boundaries. Where n = s.length.

Space — O(1)

The last map holds at most 26 entries (lowercase letters only) — effectively constant space.

Discussion

…

Loading comments…

LeetMotion