Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Partition Labels

LeetCode #763Medium
Extend the part to each letter’s last occurrence

Given a string, partition it into as many contiguous parts as possible so that each letter appears in at most one part, and return the list of part sizes in order.

Asked atAmazonGoogle
step 1 / 33
a
b
a
b
c
b
a
c
a
d
e
f
e
g
d
e
h
i
j
h
k
l
i
j
[0][1][2][3][4][5][6][7][8][9][10][11][12][13][14][15][16][17][18][19][20][21][22][23]
Greedy · cut at each letter’s last occurrence
▸
1given s
2for i ← 0 to n − 1: last[s[i]] ← i
3start ← 0;  end ← 0;  sizes ← []
4for i ← 0 to n − 1:
5    end = max(end, last[s[i]])
6    if i == end:
7        sizes.push(end − start + 1);  start ← i + 1
8return sizes
state
  • n24
  • s"ababcbacadefegdehijhklij"

line 1Partition Labels: cut "ababcbacadefegdehijhklij" into the most pieces possible so that no letter is split across two pieces. The greedy key: a partition that contains a letter MUST stretch at least to that letter's LAST occurrence — otherwise the letter would appear in two parts.