Partition Labels

Start a window at the current position. For every character currently inside the window, find its last occurrence anywhere in the string and grow the window to cover it. Keep doing this until the window stops growing — at that point every letter inside it is fully contained, so it is a valid partition boundary.

class Solution:
    def partitionLabels(self, s: str) -> list[int]:
        result = []
        i = 0
        n = len(s)
        while i < n:
            j = i
            k = i
            while k <= j:
                last = s.rindex(s[k], 0, n)
                j = max(j, last)
                k += 1
            result.append(j - i + 1)
            i = j + 1
        return result

Each rindex call scans up to the full string, and it can be called up to n times per partition, so this is O(n²) in the worst case.

Precompute the last index at which each letter appears — one pass, O(n) (bounded by 26 distinct letters in extra space). Then scan left to right, keeping end as the furthest last-occurrence seen among letters encountered so far in the current partition. The moment the current index i reaches end, every letter seen since the partition started has already had its final appearance — the partition can close right there.

class Solution:
    def partitionLabels(self, s: str) -> list[int]:
        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

Tracing s = "eccbbbbdec" (last occurrences: e→8, c→9, b→6, d→7):

Why it’s correct: a partition boundary is only ever valid at a point where no letter seen so far reappears later — and end is precisely tracking the earliest such point, since it is continuously pulled forward by every letter’s true last occurrence. Closing the partition the instant i == end produces the smallest valid partition starting there, and taking the smallest valid partition at every step is exactly what maximizes the total number of partitions — waiting longer than necessary could only merge two valid partitions into one. Complexity: two linear passes → O(n) time; extra space is O(1) since the last-occurrence map has at most 26 entries.