Partition Labels — Greedy Last-Occurrence Interval Merge

Problem Statement#

You are given a string s. Partition it 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.

Constraints:

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

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

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

Why This Problem Matters#

Partition Labels combines two ideas elegantly: tracking the last occurrence of each character, and performing a greedy interval merge. It is frequently asked by Amazon, Google, Microsoft, and Apple because it models real-world constraints in text segmentation and distributed systems (where each resource must belong to exactly one partition).

The problem is deceptively simple to understand but requires precise implementation. The key insight — that a partition boundary can only be placed where the last occurrence of every character seen so far is at or before the current position — maps directly to the interval merge pattern: each character defines an interval from first to last occurrence, and we find the minimum number of non-overlapping groups.

This is an excellent example of reducing a complex constraint to a simple greedy rule using preprocessing (the last-occurrence map) to enable linear scanning.

The Core Insight#

For each character, its interval is [first_occurrence, last_occurrence]. A valid partition boundary can only occur at position i if all characters encountered from the current partition start to position i have their last occurrence at or before i.

This gives the greedy algorithm:

1. Precompute the last occurrence index of each character.
2. Scan left to right. Track end (the furthest right any character in the current partition reaches).
3. At each position, update end = max(end, last[s[i]]).
4. When i == end, close the current partition. Record its length and start a new one.

The end variable acts like the merge boundary in interval scheduling: it expands whenever a character has a later last occurrence, and closes when the scan catches up to it.

Visual Dry Run#

s = "ababcbacadefegdehijhklij"

Last occurrences: a:8, b:5, c:7, d:14, e:15, f:11, g:13, h:19, i:22, j:23, k:20, l:21

Result: [9, 7, 8].

Solution (Optimal)#

class Solution:
    def partitionLabels(self, s: str) -> list[int]:
        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

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

Time: O(n) — two linear passes (one to build the map, one to scan) Space: O(26) = O(1) — last map holds at most 26 lowercase letters

Common Mistakes#

• Using first occurrence instead of last occurrence — last occurrence tells us how far right a partition must extend to include all copies; first occurrence is not useful for boundary detection
• Computing partition length as end - start instead of end - start + 1 — the partition includes both endpoints (inclusive), so the length is end - start + 1
• Not resetting start after closing a partition — the new partition begins at i + 1; forgetting to update start makes subsequent lengths wrong
• Updating end with i instead of last[s[i]] — end represents the last occurrence of any character in the current partition, not the current scan index
• Using i >= end instead of i == end — since end only ever increases (we take max), i reaches end exactly once per partition; == is cleaner and equivalent

Interview Tips#

• Explain the dual interpretation: "This is equivalent to interval merging. Each character defines an interval [first, last]. I merge all overlapping character intervals and return the sizes of the merged groups."
• The scan approach: "I maintain an end pointer that is the maximum last-occurrence of all characters seen so far in the current partition. When my scan index reaches end, I know this partition is self-contained."
• Note the O(1) space: "The last map holds at most 26 entries (lowercase letters). This is effectively O(1) space regardless of input size."

Follow-up Questions#

• What if each character can appear in at most k parts (instead of 1)? Track the k-th-to-last occurrence per character instead of just the last occurrence. The greedy extension logic remains similar.
• Can there be a case where the entire string must be one partition? Yes — whenever any character's last occurrence is at or near the end of the string (like 'e' and 'c' in Example 2).
• How does this relate to Merge Intervals (LC 56)? Each character defines an interval [first, last]. Partition Labels is equivalent to merging all overlapping character intervals and returning the merged interval sizes. The greedy scan implicitly performs this merge.
• What if characters can belong to multiple parts? The constraint is lifted and the maximum partition count is the string length (one character per partition if all unique).

Key Takeaways#

• Build a last_occurrence map: {char: last_index_in_string} in O(n) using {c:i for i,c in enumerate(s)}.
• Track end as the maximum last-occurrence of all characters seen in the current partition — expand it as you scan.
• A partition closes when i == end — the scan has caught up to the furthest any character extends.
• Partition length is end - start + 1 (inclusive of both endpoints); reset start = i + 1 after recording.
• Space is O(1) — only 26 possible characters bound the map size regardless of string length.
• This problem is equivalent to merging character intervals and returning the sizes of merged groups.
• The last-occurrence precomputation is the key insight that converts an O(n²) check into O(n) — same technique as used in Remove Duplicate Letters.