M.A.T.R.I.X

Appearance

Volume ITechnology

4.26.7 — Partition Labels ​

LeetCode 763 · Medium

The problem ​

Split the string into as many parts as possible, so that each letter appears in at most one part. Return the sizes of the parts.

Restating the Problem: You have a string of lowercase English letters. You want to chop it into contiguous substrings (partitions). The rule is: if a letter (like 'a') appears in one partition, all other 'a's in the string must also be in that exact same partition. You want to make as many partitions as possible.

  • Constraints to note: The string length is up to 500, which is small, but an O(n) solution is straightforward and expected. The string contains only lowercase English letters, meaning we have a fixed alphabet size of 26.
s = "ababcbacadefegdehijhklij"   →  [9,7,8]
    "ababcbaca" | "defegde" | "hijhklij"

Brute Force Approach ​

You could try all possible partitions. For a string of length n, there are n-1 places to put a cut, meaning 2^{n-1} possible ways to partition the string. For each partitioning, you'd check if any letter crosses boundaries. This O(2^n) approach is incredibly slow and completely unnecessary.

The pattern ​

A part cannot end before the last occurrence of every letter it contains. So:

Precompute the last index of each letter. Then sweep, extending the current part's end to cover every letter you meet, and cut as soon as you reach that end.

Two passes. The first builds a 26-entry table; the second is one linear sweep.

Why this is optimal. The part must extend at least to the furthest last-occurrence of anything inside it, so cutting earlier is impossible. And cutting the moment you can is what maximises the number of parts. There is no choice — the boundary is forced, exactly like 4.26.5 Hand of Straights.

The solution ​

python
class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last = {c: i for i, c in enumerate(s)}       # last index of each letter

        result = []
        start = end = 0

        for i, c in enumerate(s):
            end = max(end, last[c])                  # this part must reach here

            if i == end:                             # nothing inside reaches further
                result.append(end - start + 1)
                start = i + 1

        return result
ts
function partitionLabels(s: string): number[] {
  const last = new Map<string, number>();
  for (let i = 0; i < s.length; i++) last.set(s[i], i);

  const result: number[] = [];
  let start = 0, end = 0;

  for (let i = 0; i < s.length; i++) {
    end = Math.max(end, last.get(s[i])!);

    if (i === end) {
      result.push(end - start + 1);
      start = i + 1;
    }
  }

  return result;
}

{c: i for i, c in enumerate(s)} keeps the last index of each letter, because later assignments overwrite earlier ones. That one-liner is the whole precomputation, and it is worth noticing that a dictionary comprehension naturally keeps the last value.

end = max(end, last[c]) is the extension. Every letter you meet drags the boundary out to wherever that letter last appears.

i == end is the cut. You have walked to the furthest point anything in this part requires, so nothing inside it appears later. Cut here.

Code Walkthrough:

  • Precomputation: We first iterate through the string to build a dictionary/map last that records the final index where each character appears.
  • Initialization: We set start = 0 and end = 0 to track the boundaries of our current partition.
  • Iterating for Cuts: We loop through the string again with index i.
  • Extending the Boundary: At each character c, we check last[c]. If this character appears later in the string than our current end, we must extend end to last[c].
  • Making a Cut: If our current index i catches up to end (i == end), it means we've passed the last occurrence of every character we've seen so far in this partition. We can safely make a cut. We record the size end - start + 1 and begin a new partition at start = i + 1.

end - start + 1 is the part's length, with the +1 because both ends are included.

Trace ​

"ababcbacadefegdehijhklij"

Last occurrences: a at 8, b at 5, c at 7, d at 14, e at 15, f at 11, g at 13, h at 19, i at 22, j at 23, k at 20, l at 21.

icharend aftercut?
0a8no
1b8no
4c8no
8a8yes → part of length 9
9d14no
11f14no
13g15 (from e at 11)no
15e15yes → length 7
16…h i j k l23cut at 23 → length 8

[9, 7, 8] ✓.

Complexity ​

O(n) time — two passes. O(1) space, since the table holds at most 26 letters.

  • Time Complexity: O(n). We pass through the string of length n exactly twice: once to find the last occurrences and once to determine the partitions.
  • Space Complexity: O(1). The hash map stores at most 26 key-value pairs (one for each lowercase English letter), which uses a constant amount of extra memory.

This is an interval problem in disguise ​

Each letter defines an interval from its first to its last occurrence. Two letters must be in the same part exactly when their intervals overlap. So the parts are the connected groups of overlapping intervals — which is Merge Intervals (4.27.2).

The sweep above is merging those intervals without ever building them, because walking the string visits them in order of their start already.

Saying this out loud is the strongest thing you can do on this problem. It shows you see the structure rather than the trick, and it is why this problem sits between the greedy and interval chapters.

Where this goes next ​

  • Merge Intervals — the same merging, stated explicitly. 4.27.2.
  • Jump Game II — the same "extend the reach, then cut at the boundary" sweep. 4.26.3. These two problems have near-identical code and completely different stories, which is worth noticing once.
  • Video Stitching, Minimum Taps — interval covering with the same reach-extension loop.

What the interviewer will push on ​

"Why must a part reach the last occurrence of every letter inside it?" Otherwise that letter appears in two parts.

"Why is cutting as early as possible optimal?" The boundary is forced, and cutting at the first legal point maximises the count.

"How do you get the last occurrences?" One pass, letting later writes overwrite earlier ones.

"What is the space complexity?" O(1) — 26 letters, fixed. Say why it is constant rather than O(n).

"Is this related to any other problem?" Merge Intervals, with one interval per letter.

One thing to volunteer: the interval framing, and the fact that this is Jump Game II's loop with a different meaning. Two connections in one sentence each, and both show the pattern rather than the puzzle.

Next: 4.26.8 Valid Parenthesis String — the last greedy, where you track a range of possibilities instead of one number.