Partition Labels

Difficulty: Medium Source: NeetCode

Problem

You are given a string s. Partition the string into as many parts as possible so that each letter appears in at most one part. Return a list of integers representing the size of these parts.

Example 1: Input: s = "ababcbacadefegdehijhklij" Output: [9, 7, 8] Explanation: Partitions are "ababcbaca", "defegde", "hijhklij".

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

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Hash maps — storing the last occurrence of each character
• Greedy interval merging — expanding the current partition’s end greedily

1. Brute Force

Intuition

For each partition attempt, find the last occurrence of the first character. Then check if all characters in that range also have their last occurrence within the range. If not, expand the range. Repeat until the partition is stable, then record its size.

Algorithm

1. For each starting position start:
   • end = last_occurrence[s[start]].
   • For each index i from start to end:
     • end = max(end, last_occurrence[s[i]]).
   • Record end - start + 1, move start = end + 1.

Solution

def partitionLabels(s):
    last = {c: i for i, c in enumerate(s)}
    result = []
    start = 0

    while start < len(s):
        end = last[s[start]]
        i = start
        while i <= end:
            end = max(end, last[s[i]])
            i += 1
        result.append(end - start + 1)
        start = end + 1

    return result


print(partitionLabels("ababcbacadefegdehijhklij"))  # [9, 7, 8]
print(partitionLabels("eccbbbbdec"))                # [10]
print(partitionLabels("a"))                         # [1]

Complexity

• Time: O(n) — each character processed at most twice
• Space: O(1) — at most 26 characters in the map

2. Greedy — Single Pass with Expanding Window

Intuition

Pre-compute the last occurrence of every character. Then scan left to right, maintaining the farthest endpoint needed for the current partition (end). For each character at index i, expand end to max(end, last[s[i]]). When i == end, we’ve found a complete partition — everything from start to end is self-contained. Record the size and start a new partition.

This is greedy because at each step we greedily include only what’s necessary: the last occurrence of every character seen so far.

Algorithm

1. Precompute last[c] = last index of character c.
2. start = 0, end = 0.
3. For each i, c in enumerate(s):
   • end = max(end, last[c]).
   • If i == end: partition complete, append end - start + 1, set start = i + 1.
4. Return result.

Solution

def partitionLabels(s):
    last = {c: i for i, c in enumerate(s)}
    result = []
    start = 0
    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


print(partitionLabels("ababcbacadefegdehijhklij"))  # [9, 7, 8]
print(partitionLabels("eccbbbbdec"))                # [10]
print(partitionLabels("a"))                         # [1]
print(partitionLabels("abcabc"))                    # [6]
print(partitionLabels("abcd"))                      # [1, 1, 1, 1]

Complexity

• Time: O(n)
• Space: O(1) — 26-char alphabet, constant space

Common Pitfalls

Using first_occurrence instead of last_occurrence. The partition end must extend to the last time each character appears, not the first. Using first occurrence would allow the same character to appear in two partitions.

Not expanding end for every character in the range. When you extend the partition end, you must also check that the newly added characters don’t require further extension. The inner scan (or the single-pass greedy) handles this.

Using end = last[s[start]] and not updating as you go. If you only look at the starting character’s last occurrence, you’ll miss characters in the middle that extend the partition further.