🗓️ Day 34: Palindrome Partitioning with Backtracking

🧠 Concept Deep Dive

Today we combine palindromes with backtracking! Given a string s, we want to partition it into all possible lists of palindromic substrings.

Each partition must be a list of strings such that every string is a palindrome, and the entire original string is used.

This is a classic case of "try all combinations" using backtracking, and prune paths that don't work.

🎯 Visual Intuition

Let’s say s = "aab"

All palindromic partitions:

• ["a", "a", "b"]
• ["aa", "b"]

We try all splits at every index, and if the prefix is a palindrome, we recurse on the suffix.

Start → "a" | "ab" ✘  
      → "aa" | "b" ✔  
            → "a", "a", "b" ✔

🛠️ Key Patterns

🔁 Backtracking Template

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

  const isPalindrome = (str: string, l: number, r: number): boolean => {
    while (l < r) {
      if (str[l++] !== str[r--]) return false;
    }
    return true;
  };

  const backtrack = (start: number, path: string[]) => {
    if (start === s.length) {
      res.push([...path]);
      return;
    }

    for (let end = start; end < s.length; end++) {
      if (isPalindrome(s, start, end)) {
        path.push(s.substring(start, end + 1));
        backtrack(end + 1, path);
        path.pop();
      }
    }
  };

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

📘 Example

Input: "aab"\ Output:

[
  ["a", "a", "b"],
  ["aa", "b"]
]

Input: "a"\ Output: [["a"]]

🧪 Homework

1. Implement the partition(s: string) function from scratch.
2. Modify it to return only the number of partitions.
3. Bonus: Try memoizing isPalindrome() calls if you want extra performance.

🧠 Big-O Cheat Sheet

• Time: O(2^n) worst case — every character can either start or not start a new palindrome
• Space: O(n) recursion depth + output

🔮 Up Next

▶️ Day 35: Word Break with Memoized Recursion