294. Partition Labels

🔗 LeetCode Problem: 763. Partition Labels
📊 Difficulty: Medium
🏷️ Topics: String, Greedy, Hash Table, Two Pointers

Problem Statement

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

Return a list of integers representing the size of these parts.

Example 1:

Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits s into less parts.

Example 2:

Input: s = "eccbbbbdec"
Output: [10]

Constraints: - 1 <= s.length <= 500 - s consists of lowercase English letters.

---

🌳 Visual Understanding - The Partition Problem

The Problem We're Solving:

String: "ababcbacadefegdehijhklij"

Question: Split into maximum parts where each character 
          appears in ONLY ONE part

Valid partition:
  Part 1: "ababcbaca"
    Letters: a, b, c
    All 'a', 'b', 'c' appear ONLY in this part ✓

  Part 2: "defegde"
    Letters: d, e, f, g
    All 'd', 'e', 'f', 'g' appear ONLY in this part ✓

  Part 3: "hijhklij"
    Letters: h, i, j, k, l
    All 'h', 'i', 'j', 'k', 'l' appear ONLY in this part ✓

Answer: [9, 7, 8] (lengths of parts)

Understanding the Constraint:

Each letter appears in AT MOST ONE part:

Example with 'a':
  String: "a b a b c b a c a"
           0 1 2 3 4 5 6 7 8

  'a' appears at: indices 0, 2, 6, 8
  Last occurrence: index 8

  This means:
    First part MUST extend at least to index 8!
    Because 'a' appears at index 8
    Can't cut before index 8 (would split 'a' across parts)

  First part: "ababcbaca" (indices 0-8)
    All occurrences of 'a' are in this part ✓

Key Observations:

1. We want MAXIMUM parts
   More parts = better (as long as constraint satisfied)

2. Each character confined to ONE part
   If 'a' in part 1, NO 'a' in part 2, 3, etc.

3. Parts are CONTIGUOUS
   Can't skip characters
   Must partition in order

4. The KEY constraint:
   If character 'c' appears in a part,
   ALL occurrences of 'c' must be in that part!

The Core Insight:

For each character, find its LAST occurrence

Example: "ababcbacadefegdehijhklij"
  'a' last appears at index 8
  'b' last appears at index 5
  'c' last appears at index 7

When we start a partition:
  - We must include ALL characters we encounter
  - Each character "extends" the partition to its last occurrence
  - We can only END the partition when we've covered all extensions!

Think of it like a "reach" that keeps extending:
  Start at index 0
  See 'a' → must reach at least index 8
  See 'b' → must reach at least index 5 (already covered)
  See 'c' → must reach at least index 7 (already covered)
  At index 8: reach == current index
  → We can END the partition here! ✓

---

🧠 The AHA Moment - Greedy Extension

The Brute Force Nightmare:

Try all possible partitions:
  - After each character, decide: cut or continue?
  - 2^n possibilities for n characters!
  - Check if each partition is valid

This is O(2^n) - IMPOSSIBLE! 😰

The Key Insight - Last Occurrence

Discovery: We need to know where each character ENDS!

Think about it:

If we see character 'a' at the beginning,
we MUST include all other 'a's in the same partition.

To know when we can END the partition:
  → Track the LAST occurrence of each character!

Example: "ababcbaca"
  Last occurrences:
    'a' → index 8
    'b' → index 5  
    'c' → index 7

When building partition starting at 0:
  See 'a' at 0 → must extend to at least 8
  See 'b' at 1 → must extend to at least 5 (already covered)
  See 'a' at 2 → must extend to at least 8 (already covered)
  See 'b' at 3 → must extend to at least 5 (already covered)
  See 'c' at 4 → must extend to at least 7 (already covered)
  ...continue until index 8
  At index 8: we've covered all last occurrences!
  → Can END partition here! ✓

Visual Discovery - The Extending Boundary

String: "ababcbacadefegdehijhklij"
Index:   0123456789...

Last occurrence map:
  a → 8
  b → 5
  c → 7
  d → 14
  e → 15
  ...

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PARTITION 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Start: index 0
end: 0 (initially)

i=0: char='a'
  last['a'] = 8
  end = max(0, 8) = 8
  Think: "Must reach at least index 8"

i=1: char='b'
  last['b'] = 5
  end = max(8, 5) = 8
  Think: "Still need to reach 8"

i=2: char='a'
  last['a'] = 8
  end = max(8, 8) = 8
  Think: "Still need to reach 8"

i=3: char='b'
  last['b'] = 5
  end = max(8, 5) = 8

i=4: char='c'
  last['c'] = 7
  end = max(8, 7) = 8

i=5: char='b'
  last['b'] = 5
  end = max(8, 5) = 8

i=6: char='a'
  last['a'] = 8
  end = max(8, 8) = 8

i=7: char='c'
  last['c'] = 7
  end = max(8, 7) = 8

i=8: char='a'
  last['a'] = 8
  end = max(8, 8) = 8

  Check: i == end? (8 == 8) YES! ✓

  We've reached the boundary!
  All characters encountered have their last occurrence <= 8
  Can END partition here!

  Partition 1: "ababcbaca" (length = 9)

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PARTITION 2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Start: index 9
end: 9 (initially)

i=9: char='d'
  last['d'] = 14
  end = max(9, 14) = 14
  Think: "Must reach at least index 14"

i=10: char='e'
  last['e'] = 15
  end = max(14, 15) = 15
  Think: "Must reach at least index 15!"

...continue until i=15

i=15: char='e'
  last['e'] = 15
  end = max(15, 15) = 15

  Check: i == end? (15 == 15) YES! ✓

  Partition 2: "defegde" (length = 7)

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PARTITION 3
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Start: index 16
end: 16 (initially)

Process similarly...

i=23: last character
  end = 23

  Check: i == end? (23 == 23) YES! ✓

  Partition 3: "hijhklij" (length = 8)

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: [9, 7, 8]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

The Greedy Property

Why does this greedy approach work?

Key insight:
  We EXTEND the partition boundary as we encounter characters
  We END the partition as SOON as we've covered all characters

  This maximizes the number of partitions because:
    - We end each partition as early as possible
    - Earlier endings → more room for future partitions
    - Greedy early cuts → maximum parts!

This is OPTIMAL because:
  - We CAN'T end earlier (would split character across parts)
  - We SHOULDN'T end later (would make partition unnecessarily long)
  - Ending exactly when i == end is the perfect moment! ✓

---

🟢 Approach: Greedy with Last Occurrence Map (Optimal)

🎨 Building the Complete Solution

Step 1: Precompute Last Occurrences

For each character, find where it LAST appears

Example: "ababcbaca"
  a: appears at 0, 2, 6, 8 → last = 8
  b: appears at 1, 3, 5 → last = 5
  c: appears at 4, 7 → last = 7

Store in a map:
  last['a'] = 8
  last['b'] = 5
  last['c'] = 7

This tells us:
  If we encounter 'a', partition must extend to at least index 8
  If we encounter 'b', partition must extend to at least index 5
  If we encounter 'c', partition must extend to at least index 7

Step 2: The Greedy Algorithm

1. Build last occurrence map

2. Initialize:
   start = 0 (start of current partition)
   end = 0 (current partition must reach this index)

3. For each character at index i:
   - Update end = max(end, last[char])
   - If i == end:
     * We've reached the boundary!
     * Record partition length: end - start + 1
     * Start new partition: start = i + 1

4. Return all partition lengths

📝 Implementation - Clean and Simple

import java.util.*;

class Solution {
    public List<Integer> partitionLabels(String s) {
        // Step 1: Build last occurrence map
        int[] last = new int[26];  // For 'a' to 'z'
        for (int i = 0; i < s.length(); i++) {
            last[s.charAt(i) - 'a'] = i;
        }

        // Step 2: Find partitions
        List<Integer> result = new ArrayList<>();
        int start = 0;
        int end = 0;

        for (int i = 0; i < s.length(); i++) {
            // Extend partition to cover this character's last occurrence
            end = Math.max(end, last[s.charAt(i) - 'a']);

            // If we've reached the partition boundary
            if (i == end) {
                // Record partition length
                result.add(end - start + 1);
                // Start new partition
                start = i + 1;
            }
        }

        return result;
    }
}

🔍 Complete Dry Run

Input: s = "ababcbacadefegdehijhklij"

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 1: Build last occurrence map
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Scan entire string:
  last['a'] = 8
  last['b'] = 5
  last['c'] = 7
  last['d'] = 14
  last['e'] = 15
  last['f'] = 11
  last['g'] = 13
  last['h'] = 19
  last['i'] = 22
  last['j'] = 23
  last['k'] = 20
  last['l'] = 21

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 2: Find partitions
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

start = 0, end = 0, result = []

i=0: s[0]='a'
  end = max(0, last['a']) = max(0, 8) = 8
  i == end? (0 == 8) NO

i=1: s[1]='b'
  end = max(8, last['b']) = max(8, 5) = 8
  i == end? (1 == 8) NO

i=2: s[2]='a'
  end = max(8, last['a']) = max(8, 8) = 8
  i == end? (2 == 8) NO

i=3: s[3]='b'
  end = max(8, last['b']) = max(8, 5) = 8
  i == end? (3 == 8) NO

i=4: s[4]='c'
  end = max(8, last['c']) = max(8, 7) = 8
  i == end? (4 == 8) NO

i=5: s[5]='b'
  end = max(8, last['b']) = max(8, 5) = 8
  i == end? (5 == 8) NO

i=6: s[6]='a'
  end = max(8, last['a']) = max(8, 8) = 8
  i == end? (6 == 8) NO

i=7: s[7]='c'
  end = max(8, last['c']) = max(8, 7) = 8
  i == end? (7 == 8) NO

i=8: s[8]='a'
  end = max(8, last['a']) = max(8, 8) = 8
  i == end? (8 == 8) YES! ✓

  Partition complete!
  Length: 8 - 0 + 1 = 9
  result = [9]
  start = 9

i=9: s[9]='d'
  end = max(9, last['d']) = max(9, 14) = 14
  i == end? (9 == 14) NO

i=10: s[10]='e'
  end = max(14, last['e']) = max(14, 15) = 15
  i == end? (10 == 15) NO

i=11: s[11]='f'
  end = max(15, last['f']) = max(15, 11) = 15
  i == end? (11 == 15) NO

i=12: s[12]='e'
  end = max(15, last['e']) = max(15, 15) = 15
  i == end? (12 == 15) NO

i=13: s[13]='g'
  end = max(15, last['g']) = max(15, 13) = 15
  i == end? (13 == 15) NO

i=14: s[14]='d'
  end = max(15, last['d']) = max(15, 14) = 15
  i == end? (14 == 15) NO

i=15: s[15]='e'
  end = max(15, last['e']) = max(15, 15) = 15
  i == end? (15 == 15) YES! ✓

  Partition complete!
  Length: 15 - 9 + 1 = 7
  result = [9, 7]
  start = 16

i=16: s[16]='h'
  end = max(16, last['h']) = max(16, 19) = 19
  i == end? (16 == 19) NO

i=17: s[17]='i'
  end = max(19, last['i']) = max(19, 22) = 22
  i == end? (17 == 22) NO

i=18: s[18]='j'
  end = max(22, last['j']) = max(22, 23) = 23
  i == end? (18 == 23) NO

i=19: s[19]='h'
  end = max(23, last['h']) = max(23, 19) = 23
  i == end? (19 == 23) NO

i=20: s[20]='k'
  end = max(23, last['k']) = max(23, 20) = 23
  i == end? (20 == 23) NO

i=21: s[21]='l'
  end = max(23, last['l']) = max(23, 21) = 23
  i == end? (21 == 23) NO

i=22: s[22]='i'
  end = max(23, last['i']) = max(23, 22) = 23
  i == end? (22 == 23) NO

i=23: s[23]='j'
  end = max(23, last['j']) = max(23, 23) = 23
  i == end? (23 == 23) YES! ✓

  Partition complete!
  Length: 23 - 16 + 1 = 8
  result = [9, 7, 8]
  start = 24 (end of string)

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: [9, 7, 8]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Partitions:
  "ababcbaca" (length 9)
  "defegde" (length 7)  
  "hijhklij" (length 8)

All characters confined to their respective parts! ✓

📊 Complexity Analysis

Time Complexity: O(n)

Build last occurrence map: O(n)
Single pass through string: O(n)
Total: O(n)

OPTIMAL! Can't do better than O(n)! 🎯

Space Complexity: O(1)

last[] array: O(26) = O(1) (fixed alphabet size)
Result list: O(k) where k = number of partitions
  But k is output, not considered in space complexity

---

💡 Alternative Implementation - Using HashMap

class Solution {
    public List<Integer> partitionLabels(String s) {
        // Using HashMap instead of array
        Map<Character, Integer> last = new HashMap<>();

        // Build last occurrence map
        for (int i = 0; i < s.length(); i++) {
            last.put(s.charAt(i), i);
        }

        // Find partitions
        List<Integer> result = new ArrayList<>();
        int start = 0;
        int end = 0;

        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, last.get(s.charAt(i)));

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

        return result;
    }
}

Comparison: - Array: O(1) space, slightly faster - HashMap: More flexible, same time complexity - Both are correct!

---

🎯 Key Insights Summary

The Three Critical Points:

1. Last Occurrence is Key

For each character, we need to know its LAST position

Why?
  Because ALL occurrences must be in same partition
  So partition must extend to the LAST occurrence!

This single insight unlocks the solution! 🔑

2. Greedy Extension

As we scan, we keep EXTENDING the partition boundary

Current boundary = max last occurrence of all chars seen so far

When current index reaches boundary:
  → We've covered all characters!
  → Safe to END partition! ✓

3. Maximum Partitions = Early Cuts

We want MAXIMUM partitions
So cut as EARLY as possible
But not earlier than necessary!

The moment i == end is the EARLIEST safe cut! 🎯

---

🎓 Pattern Recognition - Greedy String Partitioning

Template for Similar Problems

// Pattern: Partition by character constraints
class Solution {
    public List<Integer> partitionString(String s) {
        // Step 1: Precompute character properties
        // (e.g., last occurrence, first occurrence, count)

        // Step 2: Scan and determine partition boundaries
        int start = 0;
        int end = 0;
        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < s.length(); i++) {
            // Update partition boundary based on constraint
            end = updateBoundary(end, s.charAt(i));

            // Check if we can end partition
            if (canEndPartition(i, end)) {
                result.add(calculateSize(start, end));
                start = i + 1;
            }
        }

        return result;
    }
}

Related Problems

- Merge Intervals (LC 56)
  Similar greedy extension concept

- Interval List Intersections (LC 986)
  Tracking boundaries

- Split Array into Consecutive Subsequences (LC 659)
  Greedy grouping with constraints

---

⚠️ Common Mistakes

// Mistake 1: Not precomputing last occurrences
for (int i = 0; i < s.length(); i++) {
    // Finding last occurrence inside loop - O(n²)! ❌
    int lastIdx = s.lastIndexOf(s.charAt(i));
}
// ✓ CORRECT: Precompute in O(n)
int[] last = new int[26];
for (int i = 0; i < s.length(); i++) {
    last[s.charAt(i) - 'a'] = i;
}

// Mistake 2: Wrong partition length calculation
result.add(end - start); // ❌ Off by one!
// ✓ CORRECT:
result.add(end - start + 1);

// Mistake 3: Forgetting to update start
if (i == end) {
    result.add(end - start + 1);
    // ❌ Forgot: start = i + 1;
}

// Mistake 4: Using wrong comparison
if (i >= end) { // ❌ Should be ==
// ✓ CORRECT:
if (i == end) {

---

📝 Quick Revision Notes

🎯 Core Concept

Problem: Partition string into max parts where each char in at most one part

Key Insight: Each character's partition must extend to its LAST occurrence

Algorithm: 1. Precompute last occurrence of each char 2. Scan string, extending partition boundary 3. When current index reaches boundary → end partition

Why It Works: Greedy early cuts maximize partitions!

⚡ Quick Implementation

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Solution {
  public List<Integer> partitionLabels(String s) {
    return greedy(s);
  }

  private List<Integer> greedy(String s) {
    // Approach: no logic, only observation
    List<Integer> res = new ArrayList<>();

    // step 1: create last occurance map (or array)
    // Consider "ababcbacadefegdehijhklij"
    // {a=8, b=5, c=7, d=14, e=15, f=11, g=13, h=19, i=22, j=23, k=20, l=21}
    HashMap<Character, Integer> lastOccurance = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);
      lastOccurance.put(c, i);
    }

    // step 2: define partition ranges
    int start = 0;
    int end = 0;

    // step 3: start traversing each character
    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);

      // "ababcbaca" becomes 1st partition where
      // each of characters appears only here
      // i = 0 => end = 8
      // All chars from i = 1 (b) to i = 7 (c) last occurances also
      // fall under this end (8). Till that time, no more partition.
      // And also, till that time, end remains 8 only.
      // Only once we reach 8, update start (indicating next partition)
      end = Math.max(end, lastOccurance.get(c));

      if (i == end) {
        res.add(end - start + 1);

        start = i + 1;
        // end anyways will get updated
      }
    }

    return res;
  }

  public static void main(String[] args) {
    Solution s = new Solution();

    System.out.println(
        s.partitionLabels("ababcbacadefegdehijhklij").equals(List.of(9, 7, 8)));
    System.out.println(
        s.partitionLabels("eccbbbbdec").equals(List.of(10)));
  }
}

🔑 Key Points

✓ Precompute last occurrences (O(n))
✓ Track extending boundary (end)
✓ Cut when i == end (earliest safe cut)
✓ Length = end - start + 1 (not end - start!)
✓ Time: O(n), Space: O(1)
✓ Greedy is optimal

🎪 Memory Aid

"Last occurrence, the key solution!"
"Extend boundary, don't be hasty!"
"When i equals end, partition we send!"
"Early cuts maximize, very wise!" ✨

---

🎉 Congratulations!

You've mastered Partition Labels!

What You Learned:

✅ Last occurrence tracking - Key to constraint satisfaction
✅ Greedy extension - Boundary keeps extending
✅ Early cutting - Maximize partitions
✅ String partitioning - New greedy pattern
✅ O(n) preprocessing - Efficiency through preparation

The Beautiful Insight:

Complex Partitioning Problem → Simple Greedy Solution

The core insight:
  "Each character's last occurrence defines boundary"

  As we scan:
    - See new character → extend to its last position
    - Boundary keeps growing
    - When we REACH the boundary → safe to cut!

  This greedy approach is optimal because:
    - Can't cut earlier (would split characters)
    - Shouldn't cut later (would reduce partition count)
    - Cutting at boundary = perfect timing! 🎯

This is the power of Greedy:
  Find the RIGHT property (last occurrence)
  Use it to make LOCAL decisions (extend boundary)
  Global optimum emerges naturally! ✨

Interview Mastery:

When asked about Partition Labels:

1. Understand: "Partition into max parts, each char in one part"

2. Key insight: "Need to know where each character ENDS!
   Precompute last occurrence of each character."

3. Algorithm: "Scan string, extend partition to last occurrence.
   When current index reaches boundary, cut partition."

4. Why optimal: "We cut as early as possible while
   respecting constraint. Early cuts = more partitions!"

5. Code it: Clean O(n) solution

6. Complexity: "O(n) time to precompute + O(n) to scan = O(n).
   O(1) space with fixed alphabet."

Shows complete understanding! 💯

You've mastered a beautiful greedy string partitioning problem! 🚀✨🎯