Medium Last Occurrence Greedy
In plain English: Split a string into the most pieces possible where no letter appears in more than one piece.
First pass: record the last occurrence of each character. Second pass: expand the current partition's end to include the last occurrence of every character encountered. When you reach the end, cut.
Prompt
Given a string s, partition it 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 = {ch: i for i, ch in enumerate(s)}
result = []
start = end = 0
for i, ch in enumerate(s):
end = max(end, last[ch]) # extend partition
if i == end: # reached the boundary
result.append(end - start + 1)
start = i + 1
return result
# Test: partition_labels("ababcbacadefegdehijhklij")
# == [9, 7, 8]
# Test: partition_labels("eccbbbbdec") == [10]