🗓️ Day 30: Palindrome Partitioning with Backtracking

🧠 Concept Deep Dive

Palindrome Partitioning is a classic use-case for backtracking. The idea is to split a string into all possible lists of palindromic substrings.

Key characteristics:

Use recursion to explore every partition
Backtrack when a substring is not a palindrome
Track path and add to result when you reach the end

🎯 Visual Intuition

Given: s = "aab"

Recursive Tree:
Start -> "a" + recurse("ab")
             -> "a" + recurse("b")
                       -> "b" + recurse("") ✅
      -> "aa" + recurse("b")
                  -> "b" + recurse("") ✅

Result: [["a","a","b"], ["aa","b"]]

We build up paths of palindromes and backtrack when needed.

🛠️ Key Patterns

♻️ Backtracking with Palindrome Check

function partition(s: string): string[][] {
  const res: string[][] = [];

  function backtrack(start: number, path: string[]) {
    if (start === s.length) {
      res.push([...path]);
      return;
    }
    for (let end = start + 1; end <= s.length; end++) {
      const substr = s.slice(start, end);
      if (isPalindrome(substr)) {
        path.push(substr);
        backtrack(end, path);
        path.pop();
      }
    }
  }

  function isPalindrome(str: string): boolean {
    let l = 0, r = str.length - 1;
    while (l < r) {
      if (str[l] !== str[r]) return false;
      l++;
      r--;
    }
    return true;
  }

  backtrack(0, []);
  return res;
}

📘 Example

Input: s = "aab"

Output: [["a","a","b"], ["aa","b"]]

Explanation: All possible palindrome partitions.

🧪 Homework

Write partition(s: string): string[][] using backtracking.
Bonus: Count how many recursive calls happen.

function partition(s: string): string[][] {
  // your code
}

🧠 Big-O Cheat Sheet

Time: O(2^n) — every char may or may not be a cut
Space: O(n) recursion stack

🔮 Up Next

▶️ Day 31: Dynamic Programming on Palindromic Substrings