LeetCode 763 · Medium · Greedy

Partition Labels

Cut the string s into as many pieces as possible so that every letter appears in only one piece. Return the sizes of the pieces in order.

O(n)time
O(1)space · 26 letters
last indexpushes the cut

lowercase letters a–z · 1–30 characters

lastIndex · letter below, its last index inside

res

public List<Integer> partitionLabels(String s) { int[] lastIndex = new int[26]; for (int i = 0; i < s.length(); i++) { lastIndex[s.charAt(i) - 'a'] = i; // later writes win } List<Integer> res = new ArrayList<>(); int size = 0; int end = 0; for (int i = 0; i < s.length(); i++) { size++; end = Math.max(end, lastIndex[s.charAt(i) - 'a']); if (i == end) { // nothing inside reaches further res.add(size); size = 0; } } return res;}
i
—
c
—
lastIndex[c-'a']
—
end
—
size
—
res
[]

Why it works

  1. Brute force tests every cut: a cut after i is legal when no letter appears on both sides. Checking each of the n cuts with set intersections costs O(n · 26) at best, O(n²) done naively.
  2. A piece must stretch to the last copy of every letter in it. So while scanning, end = the farthest last index of any letter seen in the current piece. When i reaches end, nothing inside reaches past it, and cutting here is legal and as early as possible.
  3. Cutting as early as possible maximises the count: an earlier legal cut never blocks a later one. Two passes over s, a map of at most 26 letters: O(n) time, O(1) extra space.
  4. Pitfall: end only ever grows within a piece. Use Math.max(end, lastIndex[c - 'a']), not lastIndex[c - 'a']: a later letter with an earlier last index must not pull the cut back.
  5. Related: this is Merge Intervals (56) in disguise. Each letter spans [first, last]; overlapping spans merge into one piece.