158 — Partition Labels

158 — Partition Labels

LeetCode 763 · Medium. You are given a string s. Partition s 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.

---

🍽️ Intuition

Think of every letter in s as having a "claim" on the region between its first appearance and its last appearance — no partition boundary can cut through the middle of that claim, or the letter would end up split across two parts. So a partition can only end at a position once every letter seen so far has had its last occurrence accounted for. Scanning left to right, keep extending the current partition's boundary to cover the last occurrence of every letter encountered — the moment the scan itself reaches that boundary, every letter inside the partition so far is guaranteed to never reappear later, and it's safe to close the partition there and start a new one.

---

🚩 Pattern-Recognition Cue

"Partition so each letter appears in only one part, maximize the number of parts" is the last-occurrence-boundary tell: extend a running partition boundary to the last occurrence of every character seen so far, and close the partition exactly when the scan position catches up to that boundary — the same "extend a running frontier, close it off when reached" shape as merging overlapping intervals.

---

🐢 Brute Force

For each new partition, repeatedly re-scan the rest of the string to find the true last occurrence of every character already included, growing the boundary until it stops changing.

func partitionLabelsBruteForce(_ s: String) -> [Int] {
    let chars = Array(s)
    var result: [Int] = []
    var start = 0

    while start < chars.count {
        var end = start
        var i = start

        while i <= end {
            var lastOccurrence = i
            for j in (i + 1)..<chars.count where chars[j] == chars[i] {
                lastOccurrence = j
            }
            end = max(end, lastOccurrence)
            i += 1
        }

        result.append(end - start + 1)
        start = end + 1
    }

    return result
}

// smoke test
print(partitionLabelsBruteForce("ababcbacadefegdehijhklij"))   // [9, 7, 8]
print(partitionLabelsBruteForce("eccbbbbdec"))                  // [10]

Big-O: O(n^2) time — for every position inside a growing partition, a fresh linear scan finds that character's last occurrence in the remainder of the string. O(n) space for the chars array and result.

---

🚀 Optimal

Precompute each character's last-occurrence index in one pass with a hash map, then greedily extend the current partition's boundary to the last occurrence of every character seen, closing the partition when the scan reaches that boundary.

func partitionLabels(_ s: String) -> [Int] {
    let chars = Array(s)

    var lastIndex: [Character: Int] = [:]
    for (i, c) in chars.enumerated() {
        lastIndex[c] = i
    }

    var result: [Int] = []
    var start = 0
    var end = 0

    for (i, c) in chars.enumerated() {
        end = max(end, lastIndex[c]!)
        if i == end {
            result.append(end - start + 1)
            start = i + 1
        }
    }

    return result
}

// smoke test — same cases as the brute force
print(partitionLabels("ababcbacadefegdehijhklij"))   // [9, 7, 8]
print(partitionLabels("eccbbbbdec"))                  // [10]

Big-O: O(n) time — one pass to build the last-occurrence map, one pass to greedily partition. O(n) space for the map.

---

🔑 The Key Insight

The brute force re-derives "where does this character last occur" from scratch, over and over, for every character inside every growing partition — massively redundant work since a character's last occurrence never changes. The optimal version computes every character's last occurrence exactly once, up front, so extending a partition's boundary is a constant-time lookup instead of a linear scan. The greedy close-off rule (i == end) works because once the scan reaches the current boundary, every character encountered inside the partition so far has had its last occurrence accounted for by definition — there's no way a character from this partition can reappear later, so it's always safe to cut here and never necessary to reconsider the cut.

---

🔗 Related Chapters

• Greedy — the boundary only ever extends forward and is closed the instant the scan catches up to it, the same running-frontier shape as Jump Game's farthest tracker.
• Hash Maps and Hash Sets — the last-occurrence map turns "where does this character appear last" into an O(1) lookup instead of a re-scan.
• Merge Intervals — each partition is effectively the union of every character's [firstOccurrence, lastOccurrence] interval that overlaps it, extended and merged left to right exactly like overlapping interval merging.

---

🧸 Memory Sentence

Partition Labels is a last-occurrence frontier — extend the current partition's boundary to the last occurrence of every character seen, and close it the moment the scan itself reaches that boundary.

---

✅ Check Your Understanding

1. Why does reaching i == end guarantee that no character inside the current partition can reappear later in the string?
2. Trace partitionLabels("ababcbacadefegdehijhklij") far enough to explain why the first partition ends at size 9, not sooner.
3. Why is precomputing every character's last occurrence in a separate pass strictly necessary for the O(n) bound, rather than looking it up on demand during the main scan?

---

⬅️ Previous: Merge Triplets to Form Target Triplet · Next: Valid Parenthesis String ➡️