The O(n) Club: Partition Labels: Don’t Split Before the Party’s Over

The O(n) Club: Partition Labels—Don’t Split Before the Party’s Over

⚡ TL;DR

You want to split a string into as many parts as possible so that each letter shows up in only one part. Most folks leap for brute force (and should immediately leap back). The actual move: jot down the last seen index of every character, then walk the string and only cut when you’ve reached the last required letter. Java code you’d never use in production (but definitely hackathon):

// Don't follow this! Inefficient O(n²) hack:
List<Integer> bruteForce(String S) {
    List<Integer> result = new ArrayList<>();
    int i = 0;
    while (i < S.length()) {
        Set<Character> chars = new HashSet<>();
        int j = i;
        while (j < S.length() && !chars.contains(S.charAt(j))) {
            chars.add(S.charAt(j++));
        }
        result.add(j - i);
        i = j;
    }
    return result;
}

🧠 How Devs Usually Mess This Up

Most devs, fueled by panic and caffeine, just split every time they see a repeat letter. “Duplicate? New section! Move ON!” Well, guess what? You’ll end up with wild, weird partitions that make zero sense on test cases like ababcbacadefegdehijhklij. Greedy doesn’t mean trigger-happy — it means patient like a CPU waiting for the last byte on the bus. Trust us, the job’s not done till everyone’s clocked out.

🔍 What’s Actually Going On

Imagine every character is a wildly unreliable group project member. Your job: wait until every slacker’s last update comes in, then you can officially close the chapter. Scan the string, track whose “last appearance” you need, and only split when everyone invited has signed the attendance sheet (literally, reach the furthest last index for all characters in the group so far).

Like a chef waiting for all kitchen stations to finish before serving—cutting too early means someone’s risotto is cold. So, no split until every resource (letter) is done.

🛠️ PseudoCode

• Build a Map<Character, Integer> for every character’s last index in the string.
• Walk through the string: for each letter, extend the current partition’s right boundary as far as any new last index you see.
• When current index == farthest boundary, close the partition—everyone you care about is in.
• Java-flavored skeleton:

  // Map last appearances
  for (int i = 0; i < S.length(); i++) {
      lastMap.put(S.charAt(i), i);
  }
  // Sweep
  int start = 0, end = 0;
  for (int i = 0; i < S.length(); i++) {
      end = Math.max(end, lastMap.get(S.charAt(i)));
      if (i == end) {
          res.add(end - start + 1);
          start = i + 1;
      }
  }
  

💻 The Code

import java.util.*;
 public class PartitionLabels {
    public List<Integer> partitionLabels(String S) {
        Map<Character, Integer> lastMap = new HashMap<>();
        for (int i = 0; i < S.length(); i++) {
            lastMap.put(S.charAt(i), i);
        }
        List<Integer> res = new ArrayList<>();
        int start = 0, end = 0;
        for (int i = 0; i < S.length(); i++) {
            end = Math.max(end, lastMap.get(S.charAt(i)));
            if (i == end) {
                res.add(end - start + 1);
                start = i + 1;
            }
        }
        return res;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Letters that show up once? They get their own cozy room.
• If your string’s a jumble of repeated letters (or worse, everything’s the same), prepare for one giant, awkward party partition.
• Forgetting to map last indices upfront? Have fun debugging infinity loops.
• Time/space: Two quick O(n) passes and a map of letter counts (think 26 for lowercase, more for Unicode—a real treat!).

🧠 Interviewer Brain-Tattoo

“Patience is a partitioner’s best friend—split when the night is over, not when the first guest says goodbye.”