763. Partition Labels

Partition s into as many pieces as possible so that each letter appears in at most one piece. Return the sizes of the pieces, in order.

Record each letter's last index. Scan left to right, stretching the current piece's end to the last index of every letter seen; when i reaches that end, cut.

1function partitionLabels(s: string): number[] {
2  const last = new Map<string, number>();
3  [...s].forEach((c, i) => last.set(c, i));
4  const res: number[] = [];
5  let start = 0, end = 0;
6  for (let i = 0; i < s.length; i++) {
7    end = Math.max(end, last.get(s[i])!);
8    if (i === end) { res.push(end - start + 1); start = i + 1; }
9  }
10  return res;
11}

start = 0end = 0

s

last index

d14

e15

f11

g13

h19

i22

j23

k20

l21

pieces

empty

Record each letter's last index.

1 / 0

Space: play/pause · ←/→: step