Partition Labels | Engineering Interview Kit

Concept

LeetCode #763.
Problem: You are given a string s. We want to 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.

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

Part 1: "ababcbaca". Length 9. (The letters ‘a’, ‘b’, ‘c’ only appear in this chunk).
Part 2: "defegde". Length 7. (The letters ‘d’, ‘e’, ‘f’, ‘g’ only appear in this chunk).
Part 3: "hijhklij". Length 8.

The rule: If you put an 'a' in the first chunk, you MUST put ALL other 'a's in the entire string into that exact same chunk.

The Greedy Expansion Strategy

If we look at the very first letter ('a' at index 0), we must ask: “Where is the absolute LAST occurrence of 'a' in this string?”
Let’s say the last 'a' is at index 8.
Because all 'a's must be in the same chunk, our first chunk MUST mathematically extend to at least index 8.

But what if the letter 'b' is sitting at index 1?
Because 'b' is inside our chunk, all 'b's must also be in this chunk! What if the last 'b' is at index 12?
Our chunk is forced to expand! The boundary pushes out to index 12.

The Algorithm:

Do a first pass over the string. Use a Hash Map to record the Last Known Index of every single character.
Do a second pass over the string using a Two-Pointer technique (size and end).
For every character we touch, look up its Last Known Index.
Expand the end boundary to Math.max(end, lastKnownIndex).
If our current index i exactly reaches the end boundary, it means we have perfectly encapsulated all characters within the chunk! We close the chunk, save its size, and start a brand new one.

Implementation

// Time Complexity: O(N) (Two passes over the string)
// Space Complexity: O(1) (Hash Map holds max 26 characters, which is constant space)

function partitionLabels(s: string): number[] {
    // 1. Record the LAST appearance of every character
    // Using an array of size 26 is faster than a Map, but a Map is easier to read.
    const lastIndexMap = new Map<string, number>();
    for (let i = 0; i < s.length; i++) {
        lastIndexMap.set(s[i], i);
    }

    const result: number[] = [];
    let currentChunkSize = 0;
    let currentEndBoundary = 0;

    // 2. Scan the string and expand the chunks greedily
    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        
        // Track the size of our current chunk
        currentChunkSize++;

        // The Greedy Step: Push the boundary outward!
        // (If the boundary is already at index 12, and this char's last index is 5,
        // it safely stays inside the boundary and Math.max ignores it).
        currentEndBoundary = Math.max(currentEndBoundary, lastIndexMap.get(char)!);

        // Did we reach the edge of our expanded boundary?
        if (i === currentEndBoundary) {
            // Cut the string here!
            result.push(currentChunkSize);
            
            // Reset the size for the next chunk
            currentChunkSize = 0;
        }
    }

    return result;
}

Why this is Greedy

This algorithm uses the Greedy property of Local Optimization for Global Benefit.
At every step, it only looks at the current character and greedily expands the boundary only as far as absolutely mathematically necessary for that specific character. By keeping the boundary as aggressively tight as possible, it guarantees we cut the string into “as many parts as possible”, perfectly satisfying the problem requirements without simulating multiple cuts.

Interview Questions

Q: A developer uses .lastIndexOf(char) inside the for loop instead of building a Hash Map first. Is this efficient?
A: No, this is a fatal performance error. String.prototype.lastIndexOf() is an $O(N)$ operation because it physically scans the string backward. If you put it inside an $O(N)$ for loop, the algorithm degrades into $O(N^2)$ time complexity. Building the Hash Map upfront in one pass takes $O(N)$ time, reducing the lookup inside the loop to $O(1)$ , keeping the overall time complexity at pure $O(N)$ .

Q: If the string is "abcdefg", what is the output?
A: [1, 1, 1, 1, 1, 1, 1]. The Hash Map records the last index of a as 0. When the loop starts, end is 0. i === end matches instantly! It cuts the chunk at size 1. This repeats for every character, perfectly maximizing the number of parts.