Partition Labels: Greedy String Partitioning

You are given a string s. Partition the string into as many parts as possible so that each letter appears in at most one part. Return a list of integers representing the size of these parts.

This is LeetCode 763: Partition Labels, a medium problem that combines greedy thinking with the idea of merging overlapping intervals. The trick is that you do not need to build actual intervals at all. A single left-to-right scan with one key piece of precomputed data is enough.

Why this problem matters

Partition Labels is really an interval merging problem in disguise. Every character in the string defines an implicit interval from its first occurrence to its last occurrence. Two characters that share overlapping intervals must end up in the same partition. The problem boils down to merging all overlapping character intervals and returning their sizes.

Once you see that connection, you unlock a family of related problems: Merge Intervals, Non-overlapping Intervals, and Minimum Number of Arrows. The greedy "expand the boundary" pattern used here is the same one that powers all of them.

The key insight

You only need one piece of information per character: its last occurrence in the string. With that, you can scan left to right and greedily decide where each partition ends.

Here is the idea. As you walk through the string, you track the farthest index you must reach before you can close the current partition. Every time you encounter a character, you check its last occurrence and potentially push the partition boundary further out. When your scan index catches up to the boundary, you have found a complete partition.

This works because no character inside the partition can appear outside it. The last occurrence map guarantees that.

Building the solution

def partition_labels(s):
    last = {}
    for i, ch in enumerate(s):
        last[ch] = i

    result = []
    start = 0
    end = 0

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

    return result

Step-by-step walkthrough

Let's trace through the example string "ababcbacadefegdehijhklij" to see exactly how the algorithm decides where to cut.

The algorithm makes two passes. The first pass builds the last-occurrence map in O(n) time. The second pass scans left to right, expanding the end pointer whenever a character's last occurrence extends beyond the current boundary. When i reaches end, you know every character in the range [start, end] has its last occurrence within that range. You record the partition size and move on.

Notice how the end pointer only moves forward, never backward. Each character is visited exactly once in each pass. This is what keeps the algorithm linear.

Complexity analysis

The greedy solution runs in O(n) time with two passes over the string. Space is O(1) because the last-occurrence map holds at most 26 entries (one per lowercase letter).

Edge cases to watch for

• Single character string like "a": only one partition of size 1. The loop sets end = 0, and i == end on the first iteration.
• All unique characters like "abcdef": every character's last occurrence equals its own index, so each character becomes its own partition. Result is [1, 1, 1, 1, 1, 1].
• All same character like "aaaa": the last occurrence of 'a' is 3, so the end pointer jumps to 3 immediately and you get one partition of size 4.
• Two characters interleaved like "ababab": both 'a' and 'b' have their last occurrence at the end, so the entire string is one partition.
• Already partitioned like "aabbcc": each character pair is self-contained, giving [2, 2, 2].

The building blocks

This problem is built on two reusable patterns.

1. Last-occurrence preprocessing

The first pass builds a map from each character to its rightmost index. This is a common preprocessing step that converts character-level questions into index-level questions. You will see the same pattern in problems like Longest Substring Without Repeating Characters and Minimum Window Substring, where knowing the position of characters drives the algorithm.

2. Greedy interval expansion

The second pass uses a greedy scan that maintains a "must reach" boundary. You expand the boundary whenever you find evidence that the current partition must extend further, and you close the partition only when you have exhausted all reasons to extend it. This is the same logic that powers Merge Intervals. The difference is that here the intervals are implicit (derived from character positions) rather than given as input.

From understanding to recall

You have seen the two-pass approach and it makes sense. Precompute last occurrences, then scan and expand. But can you write it from scratch in an interview without referring back to this page?

The details matter: using max(end, last[ch]) to expand (not replace), checking if i == end (not if i >= end), and remembering to update start = i + 1 after recording a partition. These are small details that are easy to confuse under pressure.

Spaced repetition closes that gap. You practice writing the two-pass solution from memory at increasing intervals until the pattern is automatic. When you see a string partitioning or interval merging problem, you do not have to reason from scratch. The code just flows.

The greedy expansion pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Merge Intervals - The classic interval merging problem that uses the same greedy expansion idea
• Non-overlapping Intervals - Finding the minimum removals to eliminate overlaps, the flip side of merging
• Minimum Number of Arrows to Burst Balloons - Another interval problem where greedy boundary tracking determines the answer

CodeBricks breaks the partition labels problem into its last-occurrence preprocessing and greedy interval expansion building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy partitioning question shows up in your interview, you do not think about it. You just write it.