MEDIUM

Partition Labels

Given a string s, split it into as many parts as possible such that each letter appears in at most one part. Return the list of part lengths.

Example

Input s = "ababcbacadefegdehijhklij"

Output [9,7,8]

Key Pointers

Every occurrence of a letter has to stay inside the same partition, so each letter's last-occurrence index tells you how far the current partition must reach at minimum.
While scanning, keep stretching the current partition's end to the last occurrence of every letter encountered so far — it can only close once the scan reaches that stretched end.
Precomputing last-occurrence indices up front turns the rest into a single linear pass with no backtracking.

Step-by-Step Analysis

Precompute lastIndex, a map from each character to the index of its last occurrence in s.
Initialize start = 0, end = 0, and an empty result list.
For each index i, character c in s: update end = max(end, lastIndex[c]).
If i == end, the partition is complete — append end - start + 1 to the result, then set start = i + 1.
Return the result after the scan finishes.

Complexity

Time: O(n) — Space: O(1) (fixed alphabet size)

Code

def partitionLabels(s: str) -> list[int]:
    lastIndex = {c: i for i, c in enumerate(s)}
    result = []
    start = end = 0

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

    return result

Code Explanation

How the solution above works, piece by piece.

lastIndex records where each letter appears for the last time.
Scan the string, extending end to the furthest last-occurrence of any letter seen in the current part.
When i == end, every letter in the part has no later copies, so the part can close here: record its size.
Start the next part at i + 1.
Two passes, O(n) time, O(26) extra space.

Visual Walkthrough

Running it on s = "ababcbacadefegdehijhklij":

Every letter must stay inside one part, so a part can only end once it has passed the last occurrence of every letter it contains. Growing end to cover those last occurrences gives parts of 9, 7 and 8.

part 1part 2part 3

Video Explanation

NeetCode — Partition Labels, LeetCode 763