Partition Labels — Greedy Last-Occurrence Interval Merging [LC 763]

Problem Statement#

Given string s of lowercase letters, partition it into as many parts as possible so that each letter appears in at most one part. Return a list of the sizes of these parts.

Constraints:

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

Input:  s = "ababcbacadefegdehijhklij"
Output: [9,7,8]

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

Why This Problem Matters#

LeetCode 763 is a popular FAANG string interview question that tests greedy interval thinking. Amazon and Google use it to verify that candidates can translate a constraint ("each letter in exactly one part") into an actionable algorithm ("track last occurrence, extend boundary when needed"). The solution is elegant: a single character-to-last-index map, then one greedy pass.

The pattern — precompute endpoints, then greedily merge overlapping intervals — appears in Merge Intervals (LC 56), Meeting Rooms, and Non-overlapping Intervals (LC 435). This problem is a gateway to that entire family.

The Core Insight#

Key observation: If character c first appears at position i, it must stay in the same partition as every other occurrence of c. The last occurrence of c defines the minimum right boundary of any partition containing c.

Algorithm:

1. Build a map last[c] = last index where character c appears
2. Scan left to right with start and end of the current partition
3. At each position i, extend end = max(end, last[s[i]]) — this character forces the partition to reach at least last[s[i]]
4. When i == end, the current partition is complete — no character in it appears beyond end. Record its size and start a new partition

The magic: each time you see a character, you might push the partition boundary right. When you finally reach that boundary, you're guaranteed no character inside has any occurrence outside it.

Visual Dry Run#

Input: "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):
        last = {c: i for i, c in enumerate(s)}  # last occurrence of each char
        result = []
        start = end = 0
        for i, c in enumerate(s):
            end = max(end, last[c])   # extend boundary to last occurrence of c
            if i == end:              # current char is the last in its group
                result.append(end - start + 1)
                start = end + 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, 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 = end + 1;
        }
    }
    return result;
};

Time: O(n) — two passes: one to build last-occurrence map, one greedy scan Space: O(1) — map has at most 26 entries (lowercase letters only)

Common Mistakes#

• Using first occurrence instead of last — the constraint is that all occurrences of a letter stay in one partition, so you need the last position
• Not extending end when seeing a character — you must check every character's last occurrence, not just the first time it appears
• Off-by-one in partition size — size is end - start + 1, not end - start
• Resetting end = 0 when starting a new partition — end should carry forward as end + 1 becomes the new start
• Confusing this with Merge Intervals — here you don't sort; the string's natural left-to-right order is the scan order

Interview Tips#

• Explain the constraint mapping: "character c must be in one partition" means the partition must span from c's first to last occurrence
• State the greedy invariant: when i == end, every character seen so far has its last occurrence at or before end
• Draw the last-occurrence map for a short example, then trace the boundary
• Highlight O(1) space: the last-occurrence map has at most 26 entries regardless of string length
• Connect to interval merging: this is essentially merging intervals [first[c], last[c]] for each character

Follow-up Questions#

• What if characters can appear in multiple partitions? (Drop the constraint — trivially partition however you like)
• What if you want to minimize the number of partitions? (Greedily merge any overlapping character intervals — same algorithm, different framing)
• What if the alphabet is Unicode (not just lowercase letters)? (Use a HashMap instead of a fixed array — same O(n) time, O(k) space where k is alphabet size)
• How does this relate to Merge Intervals? (Both use greedy boundary extension; here intervals are character spans)
• Can you return the actual partition strings instead of sizes? (Yes — use s[start:end+1] at each cut point)

Key Takeaways#

• LeetCode 763 is asked at Amazon, Google, and Meta — a clean greedy string problem requiring interval thinking
• Map each character to its last occurrence; this defines the minimum right boundary of any partition containing it
• Greedily extend end = max(end, last[s[i]]) at each step; when i == end, cut and record partition size
• Time O(n), Space O(1) — the character map has at most 26 entries for lowercase input
• The invariant when cutting: every character seen so far (index start to end) has no occurrence beyond end
• This is interval merging disguised as a string problem — the same greedy boundary extension appears in LC 56 and 435
• One pass to build the map, one pass to scan — cleanest two-pass O(n) pattern in string interviews