LeetCode 763 Partition Labels - Implementation

Two passes: record last positions, then greedily partition.

def partitionLabels(s): last = {c: i for i, c in enumerate(s)} result = [] start = end = 0

for i, c in enumerate(s):
    end = max(end, last[c])
    if i == end:
        result.append(end - start + 1)
        start = i + 1

return result

$O(n)$ time, $O(1)$ space.