DSA Tracker

Visualize

Partition Labels

Greedy farthest-last-occurrence partition cuts

time O(n)space O(1)

For every character in the string, all of its occurrences must belong to the exact same partition. The greedy insight: if a character appears at index i, the current partition MUST extend at least as far as that character's LAST occurrence in the string. As we scan left to right, we continuously update the required partition boundary to max(end, last[char]). The very first moment our scan index i catches up to end, every character seen so far is completely contained within [start, i], so we can safely cut a partition right there to maximize total parts.

Details

Animated on: s = "ababcbacadefegdehijhklij" — partition into as many parts as possible so each letter appears in at most one part.

Problem:Partition LabelsMedium

Pattern:Greedy Scheduling and Sorting

Greedy farthest-last-occurrence partition cuts

step 1 / 10

a
[0]
b
[1]
a
[2]
b
[3]
c
[4]
b
[5]
a
[6]
c
[7]
a
[8]
d
[9]
e
[10]
f
[11]
e
[12]
g
[13]
d
[14]
e
[15]
h
[16]
i
[17]
j
[18]
h
[19]
k
[20]
l
[21]
i
[22]
j
[23]

Precompute last indices: 'a'→8, 'b'→5, 'c'→7, 'd'→14, 'e'→15, 'f'→11, etc. Initialize start=0, end=0.

  • i=0· arr[0] = a
  • start=0· arr[0] = a
  • end=0· arr[0] = a
Pseudocode
1FUNCTION partitionLabels(s):
2  last = a lookup table (char → its last index in s)
3  FOR i from 0 to length of s - 1: store s[i] → i in last
4  ans = empty list, start = 0, end = 0
5  FOR i from 0 to length of s - 1:
6    end = the larger of end and the last index of s[i]
7    IF i equals end:
8      append (end - start + 1) to ans
9      start = i + 1
10  RETURN ans

← / → step · space play · Home restart

Every step in words

Show all 10 steps
  1. Precompute last indices: 'a'→8, 'b'→5, 'c'→7, 'd'→14, 'e'→15, 'f'→11, etc. Initialize start=0, end=0.
  2. i=0 (char 'a'): last['a'] = 8, so end expands to 8. The partition must reach at least index 8 to include all 'a's.
  3. Scanning i=1..4 ('b', 'a', 'b', 'c'): last['b']=5 and last['c']=7 are both <= end=8, so end remains 8.
  4. i=8 reaches end=8. Every char in [0..8] has all occurrences inside this window. Cut partition 1: length = 8 - 0 + 1 = 9. ans=[9].
  5. Set start=9. At i=9 ('d'): last['d'] = 14, so end expands to 14.
  6. i=10 (char 'e'): last['e'] = 15 > 14, extending end to 15. ('f' at idx 11 has last['f']=11 <= 15, 'g' at idx 13 has last['g']=13 <= 15).
  7. i=15 reaches end=15. All chars in [9..15] are self-contained. Cut partition 2: length = 15 - 9 + 1 = 7. ans=[9, 7].
  8. Set start=16. i=16 ('h') sets end=19, i=17 ('i') extends end=22, and i=18 ('j') extends end to 23 (last char).
  9. Scan reaches i=23 = end=23. Cut partition 3: length = 23 - 16 + 1 = 8. ans=[9, 7, 8].
  10. String partitioned into 3 parts of lengths [9, 7, 8] ("ababcbaca", "defegde", "hijhklij"). Return [9, 7, 8].

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Partition Labels in the editorAll Greedy problemsBack to roadmap