Visualize

Pattern visualizer

Partition Labels

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. Animated on: s = "ababcbacadefegdehijhklij" — partition into as many parts as possible so each letter appears in at most one part..

Greedy farthest-last-occurrence partition cuts

time O(n)space O(1)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]
line 4

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

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

Where to practice Greedy

Practice Greedy problemsAll Greedy problemsBack to roadmap