Greedy Algorithms - Partition Labels
Consider the following buggy code for partitioning labels. Which line contains the subtle bug that can cause incorrect partitions?
def partitionLabels(s):
last = [0] * 26
for i, c in enumerate(s):
last[ord(c) - ord('a')] = i
res = []
start = 0
end = 0
for i, c in enumerate(s):
end = last[ord(c) - ord('a')] # Bug here: missing max()
if i == end:
res.append(end - start + 1)
start = i + 1
return res