Back to Problem
Official 1423 views

Editorial: Partition Labels

by admin ·

24

1 Intuition

A part must extend at least to the last occurrence of every letter inside it.

2 Approach

Record each letter's last index, then sweep, extending the current part's end; close the part when i reaches that end.

3 Complexity Analysis

Time O(n), Space O(1).

4 Solution Code 

class Solution:
    def partitionLabels(self, s: str) -> list[int]:
        last = {c: i for i, c in enumerate(s)}
        out, start, end = [], 0, 0
        for i, c in enumerate(s):
            end = max(end, last[c])
            if i == end:
                out.append(end - start + 1)
                start = i + 1
        return out

5 Code Walkthrough

The reference solution below implements the approach step by step.