Partition Labels - Implementation

Here is the solution:

function partitionLabels(s)
 lastIndex := map from char to int
 for i from 0 to length - 1
 lastIndex[s[i]] := i
 result := []
 start := 0
 end := 0
 for i from 0 to length - 1
 end := max(end, lastIndex[s[i]])
 if i = end then
 result.add(end - start + 1)
 start := i + 1
 return result

Time: $O(n)$. Space: $O(1)$ since alphabet is constant size.

When $i$ reaches $end$, all characters in $[start, end]$ have their last occurrences within this range. Safe to cut here.