Medium Greedy Choice Greedy
In plain English: Split a string into the most pieces possible where no letter appears in more than one piece.
Record each character's last occurrence. Extend the current partition's end to cover all characters' last positions — cut when you reach the end.
Prompt
Partition a string into as many parts as possible so that each letter appears in at most one part. Return the sizes of the parts.
Try to write it from scratch before scrolling down.
Solution
def partition_labels(s):
last = {c: i for i, c in enumerate(s)}
sizes = []
start = end = 0
for i, c in enumerate(s):
end = max(end, last[c]) # extend to cover last occurrence
if i == end:
sizes.append(end - start + 1)
start = i + 1
return sizes
# Test: partition_labels("ababcbacadefegdehijhklij") == [9, 7, 8]