Description
Split a lowercase string into as many contiguous parts as possible so each letter appears in only one part. Return the length of each part in order.
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])
if i == end:
result.append(end - start + 1)
start = i + 1
return resultExamples
Example 1
- Input
["ababcbacadefegdehijhklij"]- Output
[9,7,8]
Three maximal partitions keep each letter local.
Example 2
- Input
["eccbbbbdec"]- Output
[10]
The repeated e and c force one whole-string part.
Example 3
- Input
["abc"]- Output
[1,1,1]
Each letter appears once and can stand alone.
Approach
Record each letter's last index. Scan the string, extending the current part's end to cover every encountered letter's last appearance. When the scan reaches that end, close the part.
Time & space
O(n) time and O(1) auxiliary space excluding output for 26 letters, where n is string length.