Partition Labels (LeetCode 763)

The problem

Given a string s of lowercase letters, split it into as many parts as possible so that each letter appears in at most one part. Joining the parts back in order must give s. Return the list of part lengths.

Input:  s = "ababcbacadefegdehijhklij"
Output: [9, 7, 8]

The parts are "ababcbaca", "defegde" and "hijhklij". No letter appears in two of them, and you can’t cut any of them smaller without splitting a letter.

How to think about it

Start with brute force. For every possible cut position, check whether any letter appears on both sides. Checking a cut is O(n), and you need to do it for every position, so O(n²). It works but repeats the same scanning again and again.

The key insight: a part must reach the last occurrence of every letter inside it. If the current part contains an a, it can’t end before the last a in the string. And every letter picked up on the way there pushes the end further out. So precompute last[c] for each letter. Then scan left to right, keeping end = max(end, last[c]). When the scan index equals end, nothing inside the part appears later, so you can cut right there.

Cutting as early as possible is optimal. Closing a part the moment it becomes legal leaves the most room for later parts, which maximises the count. Any later cut would merge parts you could have kept separate.

Which pattern is this? Greedy interval merging. Each letter defines an interval from its first to its last occurrence, and the parts are the merged groups of overlapping intervals. The tell is “as many parts as possible” with a “nothing may cross a boundary” rule.

Approach

1. Build last, mapping each letter to the index of its last occurrence.
2. Set start = 0 and end = 0.
3. Scan each index i with letter c. Set end = max(end, last[c]).
4. If i == end, the current part is closed. Append its length end - start + 1 and set start = i + 1.
5. Return the list of lengths.

Solution

def partition_labels(s):
    last = {c: i for i, c in enumerate(s)}      # later indices overwrite earlier ones
    res = []; start = end = 0
    for i, c in enumerate(s):
        end = max(end, last[c])                  # the part must reach this letter's last spot
        if i == end:                             # nothing in the part appears later: cut
            res.append(end - start + 1); start = i + 1
    return res
# partition_labels("ababcbacadefegdehijhklij") -> [9,7,8]

Dry run

last is a:8, b:5, c:7, d:14, e:15, f:11, g:13, h:19, i:22, j:23, k:20, l:21. Showing only the steps where end moves or a cut happens:

The answer is [9, 7, 8].

Complexity

• Time: O(n). One pass to build last, one pass to scan.
• Space: O(1). last holds at most 26 entries. The output list is not counted.

Edge cases and pitfalls

• Single letter ("a") gives [1].
• All distinct letters gives a list of ones, one part per character.
• One letter at both ends ("abca") forces the whole string into one part: [4].
• Using the first occurrence instead of the last cuts too early and splits a letter.
• Returning the parts instead of lengths: read the question; LeetCode wants lengths.

Related problems

• Merge Intervals (LeetCode 56): the same idea, with letter spans as the intervals.
• Jump Game II (LeetCode 45): extend a far edge while scanning and act when the index reaches it.
• Remove Covered Intervals (LeetCode 1288): another sweep that tracks the furthest end seen so far.