The O(n) Club: Palindrome Partitioning – Chop That String Like a Paranoid Chef

The O(n) Club: Palindrome Partitioning – Chop That String Like a Paranoid Chef

⚡ TL;DR

Given a string, split it every way you can so every part is a palindrome. Brute force all endings (but be smart and skip bad slices). Quick Java flavor:

// Java snippet
public List<list>> partition(String s) {
    List<list>> result = new ArrayList<>();
    backtrack(result, new ArrayList<>(), s, 0);
    return result;
}
private void backtrack(List<list>> result, List<string> temp, String s, int start) {
    if (start == s.length()) result.add(new ArrayList<>(temp));
    for (int end = start + 1; end <= s.length(); end++) {
        String sub = s.substring(start, end);
        if (isPalindrome(sub)) {
            temp.add(sub);
            backtrack(result, temp, s, end);
            temp.remove(temp.size() - 1);
        }
    }
}
private boolean isPalindrome(String str) {
    int l = 0, r = str.length() - 1;
    while (l < r) if (str.charAt(l++) != str.charAt(r--)) return false;
    return true;
}</string></list></list></list>

🧠 How Devs Usually Mess This Up

Everyone wants this to be a dynamic programming problem. Sorry, DP diehards. You need all the partitions, not just the number or shortest combo. It’s not a “find min splits” drama—it’s a “rewrite the phonebook with every legal split” situation. Others try to check if the whole partition is palindromic at the end, which is like building an Ikea desk first, then checking which bolts you were supposed to use. Order matters: ["a","a","b"] and ["aa","b"] are different. If you miss that, prepare to see a very disappointed recruiter face.

🔍 What’s Actually Going On

Think of slicing a baguette where every chunk has to read the same front and back—palindromic sandwiches! At every crumb, you check: is this slice a palindrome? If so, slice again. If not, scoff and backtrack to the previous cut—like a chef who can’t bear unsymmetrical bread.

We’re using backtracking (a.k.a. “try-every-door-until-you-find-your-socks”). Each substring gets a go. If it’s pretty (palindromic), we continue; otherwise, nope. Reach the end after enough good slices? Save that magical bake. Rinse and repeat until you’ve burned through all possibilities.

🛠️ PseudoCode

• Start with an empty list and position 0. This is your chopping board.
• For every end from start + 1 up to s.length():
  • Grab s.substring(start, end).
  • If that sub is a palindrome, toss it on your plate and recursively try the next cut (start = end).
  • Not a palindrome? Toss it in the bin and keep looping.
• When start == s.length(), you’ve finished a valid split. Copy your current list, stick it in the results fridge.
• After each recursive step, remove the last sub (so your board is tidy for the next round). No one likes a messy chef.

💻 The Code

import java.util.*;
public class PalindromePartitioning {
    public List<list>> partition(String s) {
        List<list>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), s, 0);
        return result;
    }
    private void backtrack(List<list>> result, List<string> curr, String s, int start) {
        if (start == s.length()) {
            result.add(new ArrayList<>(curr));
            return;
        }
        for (int end = start + 1; end <= s.length(); end++) {
            String sub = s.substring(start, end);
            if (isPalindrome(sub)) {
                curr.add(sub);
                backtrack(result, curr, s, end);
                curr.remove(curr.size() - 1);
            }
        }
    }
    private boolean isPalindrome(String str) {
        int left = 0, right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left++) != str.charAt(right--)) return false;
        }
        return true;
    }
    public static void main(String[] args) {
        PalindromePartitioning chef = new PalindromePartitioning();
        System.out.println(chef.partition("aab"));
        // Output: [[a, a, b], [aa, b]]
    }
}
</string></list></list></list>

⚠️ Pitfalls, Traps & Runtime Smacks

• Order is everything. Don’t let the interviewer trip you up with “combinations”—these are permutations of splits.
• Edge cases? Empty string? Returns []. Single character? Just itself, chef! All substrings of size 1 are palindromes. Try not to faint.
• Premature optimization: Sure, you could prefill a palindrome table (DP-style), but you’ll only impress LeetCode leaderboards, not interviewers.
• Runtime reality check: Yes, it’s exponential. If anyone expects you to run this for n = 25, they also think Bubble Sort is coming back.

🧠 Interviewer Brain-Tattoo

“The backtracking chef doesn’t ask if there’s a faster recipe. The chef just keeps slicing till every bite’s a palindrome—then moves on to the next loaf.”