Partition Labels

Partition Labels sounds harder than it is. You cut a string into pieces. The rule is that no letter may appear in two different pieces. So if a letter shows up, its whole run must stay inside one piece. The slow way treats every letter as an interval and merges them. The fast way sweeps once with a single boundary. That sweep is the trick the interviewer wants.

🎯 The Problem

You get a string of lowercase letters and cut it into as many pieces as possible.

• Each letter may belong to only one piece.
• So every spot where a letter appears must sit in the same piece.
• You return the size of each piece, in order.

Let us say the string is "ababcbacadefegdehijhklij". The first piece is "ababcbaca", of length 9. Why must it stretch that far? Because a appears late in it, so the piece cannot close before the last a. The full answer is [9, 7, 8].

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

Explanation: The pieces are "ababcbaca", "defegde", "hijhklij". No letter crosses a cut.

The number that decides everything is the last occurrence of each letter, which is the rightmost spot where it appears. Here is a small string "abac" showing how the first piece must reach the last a.

🐢 Approach 1: Merge Letter Intervals (Brute Force)

The idea in one line: turn each letter into a range, then merge the ranges that overlap.

The idea:

• An interval is a range from a letter’s first spot to its last spot.
• Record a start and an end for every letter.
• Merge overlapping intervals, like clashing meeting times.

How it works:

• Two letters that overlap must share a piece, so merge them.
• Each merged block becomes one piece.
• The piece sizes come from the merged ranges.

Why it is weak:

• You build a range for every letter.
• Then you sort and merge them.
• Sorting makes it O(n log n), plus extra memory for the list.

Here is the interval-merge code:

def partition_labels(s):
    intervals = []
    for ch in set(s):
        intervals.append([s.index(ch), s.rindex(ch)])
    intervals.sort()

    merged = []
    for start, end in intervals:
        if not merged or start > merged[-1][1]:
            merged.append([start, end])
        else:
            merged[-1][1] = max(merged[-1][1], end)

    return [end - start + 1 for start, end in merged]

⚡ Approach 2: Greedy Last Occurrence (Best)

The idea in one line: record each letter’s last spot, then close a piece the moment your index reaches the farthest last spot inside it.

The idea:

• You do not need intervals or sorting.
• You only need the last occurrence of each letter.
• That is the rightmost index where the letter appears.

How it works:

• First pass: record the last index of every letter.
• Then sweep with two markers, a start and an end.
• At each character, stretch end to the bigger of end and that letter’s last index.
• When the index meets end, no letter inside appears later.
• So cut here, record the length, and start the next piece.

Why it works:

• A piece can only close once every letter inside has had its last spot.
• The index meeting the farthest reach is exactly that moment.
• This is the same farthest-reach trick as Jump Game.

Why it is fast:

• Two linear sweeps and a fixed-size letter map.
• No sorting. So the time is O(n).

Here is a dry run on "abac". Watch the end marker move and the cut happen.

Steps to Solve

1. Do one pass and record the last index where each letter appears.
2. Set start = 0 and end = 0 for the current piece.
3. Walk the string. At each index, stretch end to the bigger of end and that letter’s last index.
4. When the index equals end, the piece is complete. Its length is end - start + 1.
5. Save that length. Set start to the next index for the new piece.
6. Keep going until the string ends. The saved lengths are the answer.

#include <stdio.h>
#include <string.h>

void partitionLabels(const char *s) {
    int last[26];
    int n = (int)strlen(s);
    for (int i = 0; i < n; i++) {
        last[s[i] - 'a'] = i;     // record last spot of each letter
    }
    int start = 0, end = 0;
    printf("[");
    int first = 1;
    for (int i = 0; i < n; i++) {
        int le = last[s[i] - 'a'];
        if (le > end) {
            end = le;             // stretch the piece end
        }
        if (i == end) {           // clean cut here
            if (!first) printf(", ");
            printf("%d", end - start + 1);
            first = 0;
            start = i + 1;        // next piece begins
        }
    }
    printf("]\n");
}

int main(void) {
    partitionLabels("ababcbacadefegdehijhklij");
    return 0;
}

[9, 7, 8]

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

vector<int> partitionLabels(string s) {
    int last[26] = {0};
    for (int i = 0; i < (int)s.size(); i++) {
        last[s[i] - 'a'] = i;     // last spot of each letter
    }
    vector<int> result;
    int start = 0, end = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        end = max(end, last[s[i] - 'a']);  // stretch the end
        if (i == end) {                    // clean cut
            result.push_back(end - start + 1);
            start = i + 1;
        }
    }
    return result;
}

int main() {
    vector<int> res = partitionLabels("ababcbacadefegdehijhklij");
    cout << "[";
    for (int i = 0; i < (int)res.size(); i++) {
        cout << res[i];
        if (i + 1 < (int)res.size()) cout << ", ";
    }
    cout << "]" << endl;
    return 0;
}

[9, 7, 8]

import java.util.ArrayList;
import java.util.List;

public class PartitionLabels {
    public static List<Integer> partitionLabels(String s) {
        int[] last = new int[26];
        for (int i = 0; i < s.length(); i++) {
            last[s.charAt(i) - 'a'] = i;   // last spot of each letter
        }
        List<Integer> result = new ArrayList<>();
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, last[s.charAt(i) - 'a']);  // stretch end
            if (i == end) {                // clean cut
                result.add(end - start + 1);
                start = i + 1;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(partitionLabels("ababcbacadefegdehijhklij"));
    }
}

[9, 7, 8]

def partition_labels(s):
    last = {c: i for i, c in enumerate(s)}  # last spot of each letter
    result = []
    start = 0
    end = 0
    for i, c in enumerate(s):
        end = max(end, last[c])    # stretch the piece end
        if i == end:               # clean cut here
            result.append(end - start + 1)
            start = i + 1          # next piece begins
    return result


print(partition_labels("ababcbacadefegdehijhklij"))

[9, 7, 8]

function partitionLabels(s) {
  const last = {};
  for (let i = 0; i < s.length; i++) {
    last[s[i]] = i;            // last spot of each letter
  }
  const result = [];
  let start = 0;
  let end = 0;
  for (let i = 0; i < s.length; i++) {
    end = Math.max(end, last[s[i]]); // stretch the piece end
    if (i === end) {                 // clean cut
      result.push(end - start + 1);
      start = i + 1;                 // next piece begins
    }
  }
  return result;
}

console.log(partitionLabels("ababcbacadefegdehijhklij"));

[ 9, 7, 8 ]

Let us walk through the Python version line by line, because the two-pass idea is the whole solution.

last = {c: i for i, c in enumerate(s)} builds the map of last positions. As enumerate walks the string, each letter c keeps overwriting its stored index with the latest i. So at the end every letter maps to its rightmost spot.

result = [] will hold the piece lengths. start = 0 and end = 0 mark the current piece. start is where it begins, end is how far it must reach so far.

for i, c in enumerate(s): sweeps the string again, this time to cut.

end = max(end, last[c]) is the greedy stretch. The current letter forces the piece to reach at least its last spot. We keep whichever reach is larger.

if i == end: is the cut point. When the index catches up to the farthest reach, no letter in this piece appears later. So we can close it safely.

result.append(end - start + 1) records the length of this piece. start = i + 1 moves the start to the next character for the new piece.

return result gives the list of sizes once the sweep is done.

⏱️ Time and Space Complexity

The interval way builds and sorts ranges, so it runs around O(n log n) and uses extra memory for the list. The greedy way sweeps twice and keeps only a tiny map of at most 26 letters. So it trades almost no memory and still wins. That takes the time down to O(n) with O(1) extra space, since the letter map is a fixed size.

🧩 Key Takeaways

• ✅ A piece can close only after every letter inside it has had its last spot.
• ✅ Record each letter’s last occurrence in one quick pass first.
• ✅ Sweep again, stretching the piece end to the bigger of itself and the current letter’s last spot.
• ✅ When the index meets the end, make a clean cut and record the piece length.
• ✅ This runs in O(n) time with O(1) extra space, beating the interval merge.

🚀 What’s Next?

• Jump Game
• Gas Station