Partition Labels

Medium#763

You get a string of lowercase letters. Cut it into as many parts as you can so that each letter appears in only one part, and return the lengths of the parts in order. Our example: "cabcdbefegfh" — the answer is [6, 5, 1]: "cabcdb", "efegf" and "h".

763 Partition LabelsWalkthrough · 1×

Example: "cabcdbefegfh". end is the farthest place the current part must reach; the arc goes from i to the last time its letter appears.

0c1a2b3c4d5b6e7f8e9g10f11hsizes—
not reachedmust be in the current partcurrent index iin a finished part

The last index of each letter: c 3, a 1, b 5, d 4, e 8, f 10, g 9, h 11

01/47
restart · back · play · step
Speed
1function partitionLabels(s):
2 last = the last index of each letter in s
3 sizes = []
4 start = 0
5 end = 0
6 for i from 0 to len(s) - 1:
7 end = max(end, last[s[i]])
8 if i == end:
9 add end - start + 1 to sizes
10 start = i + 1
11 return sizes
state
sizes
–
start
–
end
–
i
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. A part that holds a letter has to reach that letter's last occurrence. So end, the farthest last occurrence of the letters seen in the part, is the shortest the part can be.
  2. When i reaches end, no letter of the part appears later, so cutting there is allowed. Cutting at the first such place leaves the most room for the parts after it, which gives the most parts.
  3. Like the reach on the card, end only grows inside a part, so one pass with one number is enough.

Complexity

Time O(n): one pass to find the last indices and one to cut. Memory O(1): the last index of at most 26 letters.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.