Given a string, the machine must split it into the maximum number of contiguous parts such that every character appears in exactly one part. No character may straddle a boundary, so once a letter appears inside a part, all of its occurrences must be inside that same part.
The key insight is that each character's last occurrence is a hard deadline: a part containing a character must extend at least to that character's final index. The machine therefore scans with a growing right boundary that is the maximum of every last-occurrence seen so far, and cuts the part exactly when the scan reaches that boundary.
The approach runs in three steps. First, record the last index of every character in a single pass. Second, scan the string again, extending the current part's end to the latest last-occurrence encountered. Third, when the scan index equals the end, close the part, record its length, and reset the start for the next part. Time is O(n) and space is O(1), since the alphabet is bounded at 26 letters.
The trickiest edge case is the string that refuses to split: when the first character's last occurrence sits at the very end, the boundary never closes early and the machine must return the whole string as one part. The window logic handles this naturally, because end only grows until it reaches the final index.
def partitionLabels(s):
last = {c: i for i, c in enumerate(s)}
parts, start, end = [], 0, 0
for i, c in enumerate(s):
end = max(end, last[c])
if i == end:
parts.append(i - start + 1)
start = i + 1
return parts