Partition Labels

GREEDY · MEDIUM

The problem

You’re given a string s. Cut it into as many contiguous pieces as possible so that every letter that appears in s ends up entirely inside just one piece — no letter is allowed to appear in two different pieces. Concatenating the pieces back together in order must reproduce s exactly. Return the length of each piece, in order.

Canonical example: s = "ababcbacadefegdehijhklij" → [9, 7, 8]. The first 9 characters (ababcbaca) contain every occurrence of a, b, and c — none of those letters shows up again after index 8, so the first piece can safely close there.

Solution 1: Brute force — re-scan the whole string for every character

The naive way to check “is it safe to close the partition here?” is to look, for every character currently inside the growing window, at where else in the entire string that character shows up — by scanning from index 0 to the end every single time. If any of those re-scans turns up an occurrence past the current window boundary, the window has to grow and the newly-included characters need re-scanning too. Only once a full pass over the window confirms no character spills past it does the partition close.

function partitionLabelsBrute(s) {
  const result = [];
  let start = 0;
  while (start < s.length) {
    let end = start;
    let i = start;
    while (i <= end) {
      const c = s[i];
      let last = i;
      for (let j = 0; j < s.length; j++) {
        if (s[j] === c) last = j;
      }
      if (last > end) end = last;
      i++;
    }
    result.push(end - start + 1);
    start = end + 1;
  }
  return result;
}

Line by line:

The outer while (start < s.length) starts a fresh partition at whatever index the previous one left off at.
The inner while (i <= end) is the window-growth loop — end can move forward mid-loop, which is exactly what lets the window keep expanding as long as it needs to.
The for (let j = 0; j < s.length; j++) loop is the wasteful part: it re-scans the entire string, from index 0, just to find where one character last occurs — and this runs once per character inside the window, not once per partition.
if (last > end) end = last grows the window only when the re-scan actually found something past the current boundary.

Interactive visualization

s = "eaaabbbccd" — trace the window growth and character re-scanning

Press play to run the brute force algorithm.

Step 0 / 17

This animation traces s = "eaaabbbccd" — a short case, kept separate from the canonical example above so the whole trace stays watchable.

Complexity: O(n²) time, O(1) extra space.

Solution 2: Optimal — precomputed last-occurrence map, one pass

Every one of those re-scans is answering the same question over and over: “where does this character last appear?” That answer never changes once s is fixed, so compute it once, for every character, in a single O(n) pass, and store it in a map. Then walk s exactly once, growing a running boundary end to Math.max(end, lastOccurrence[s[i]]) at every index. The moment the scan index i catches up to end, every character seen so far is guaranteed to have shown its last occurrence already — the partition is safe to close.

function partitionLabelsOptimal(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 = i + 1;
    }
  }
  return result;
}

Line by line:

The first loop builds last, mapping every character to the highest index it occurs at. Because it always overwrites with the current index, whatever’s left after the loop is necessarily each character’s LAST occurrence.
end = Math.max(end, last[s[i]]) is the entire greedy rule: the current partition can never close before the last occurrence of ANY character it has already swallowed.
if (i === end) is the closing condition — once the scan pointer walks all the way up to the boundary without end having moved further out, there’s nothing left pending, so it’s safe to cut here.
start = i + 1 resets the window for the next partition, right after recording the size of the one that just closed.

Interactive visualization

s = "eaaabbbccd" — same string as above, showing how the precomputed map eliminates rescans

Press play to run the optimal algorithm.

Step 0 / 12

Same string as above, s = "eaaabbbccd", so the two traces are directly comparable.

Complexity: O(n) time, O(1) extra space — one pass to build the map, one pass to scan. The map is bounded by the 26-letter lowercase alphabet.

Complexity comparison

Solution	Time	Space
Brute force (re-scan per character)	O(n²)	O(1) extra
Optimal (last-occurrence map + one scan)	O(n)	O(1) extra

Interview corner

Q: Couldn’t a character re-appear later and ruin a partition that already looked closed?

No — that’s exactly what end = Math.max(end, last[s[i]]) prevents. The moment any character enters the current window, its LAST occurrence anywhere in the string immediately extends end to cover it. The scan pointer i only reaches end after every character between start and end has already contributed its own last occurrence to that same boundary — there’s no future re-appearance left to discover.

Q: Does this greedy approach guarantee the MAXIMUM possible number of partitions, or just some valid partition?

It guarantees the maximum. Any valid cut point must occur at an index where no letter seen so far reappears later — call these “safe” indices. The algorithm closes at the very first safe index it reaches (i === end the instant that condition becomes true) — it never waits or over-extends. Since closing earlier can only create room for more partitions later (never fewer), taking every safe index the moment it appears is what maximizes the count.

Follow-up: “Is this greedy choice exchange-argument provable?” Yes — swapping an earlier valid cut for a later one can never increase the total count and can only merge pieces, so greedy-closing-earliest dominates any other strategy.

Q: How would the approach change if the goal were to MINIMIZE the number of partitions instead?

Trivial — the whole string is always one valid partition, so the minimum is always 1 (just return [s.length]). There’s no interesting algorithm to design for “minimize,” which is why this problem is always phrased as maximizing — that’s the version with real constraints to reason about.

Q: Trick question — what does this log?

const last = {};
const s = "9213";
for (let i = 0; i < s.length; i++) last[s[i]] = i;
console.log(Object.keys(last));

Answer: ['1', '2', '3', '9'] — NOT ['9', '2', '1', '3'], the insertion order.

Plain object keys that look like non-negative integers (a JS spec concept called “array index” keys) are always iterated in ascending numeric order first, before any string keys, regardless of insertion order. A Map has no such special case — new Map() always preserves true insertion order for every key type.

⚠ Trap: This can’t bite the actual last map in this problem’s real code — LeetCode guarantees s is lowercase English letters only, so its keys are never numeric-looking strings. But the moment a “map keyed by characters” gets reused for digits, tokens, or any string that could be integer-like, reaching for Map instead of {} avoids this silently-reordered-keys surprise entirely.

Quiz

1. Why does the algorithm wait until the scan index i equals end to close a partition, instead of closing the instant end updates?

(correct) Every index between the current position and the new end still needs to be scanned — closing early could cut through a character’s own last occurrence
Closing early would make the algorithm run faster
There’s no real reason — closing immediately would work identically

2. What would go wrong if last[c] stored each character’s FIRST occurrence instead of its last?

(correct) Partitions could close too early, splitting a character’s occurrences across two pieces — an invalid result
Nothing — the algorithm would produce the exact same output either way
It would just run faster with no change in correctness

3. What specifically makes the optimal solution O(n) instead of O(n²)?

(correct) Each character’s last occurrence is looked up in O(1) from a precomputed map, instead of being found by re-scanning the whole string
It’s tested on shorter example strings
It skips checking some characters entirely

4. Can the greedy algorithm ever produce an INVALID partition — one that splits a single character’s occurrences across two pieces?

(correct) No — end is always extended to cover every occurrence of every character already in the window, so a split can’t happen
Only on very long strings, due to floating point limits
Yes, if the string isn’t sorted alphabetically first

5. Why does closing at the FIRST safe index guarantee the MAXIMUM number of partitions, rather than just A valid partition?

(correct) Any later cut point could only merge pieces that were already safe to split — never create additional ones — so taking every earliest safe cut maximizes the count
It doesn’t guarantee the maximum — it’s just one of several equally valid partitions
Because the alphabet is fixed at 26 letters, there’s only ever one possible partition