🗓️ Day 38: Palindrome Partitioning — All Ways to Split

🧠 Concept Deep Dive

Given a string s, partition it so that every substring in the partition is a palindrome. Return all possible palindrome partitioning of s.

This is a classic Backtracking + Dynamic Programming (pruning) problem. We try all ways to split the string, but we only proceed with a split if the substring is a palindrome.

🎯 Visual Intuition

For s = "aab", the possible partitions are:

[
  ["a", "a", "b"],  // all single-character palindromes
  ["aa", "b"]       // "aa" is a palindrome
]

We move character by character, try slicing the string from the start to i, and recursively explore the rest — but only if the current slice is a palindrome.

🛠️ Code Pattern: Backtracking with Palindrome Check

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

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

  function 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.slice(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. What if the input string is empty?
2. Count the number of valid palindrome partitions.
3. Optimize palindrome checking with DP memoization.

🧠 Big-O Cheat Sheet

• Time: O(N * 2^N) — exploring all partitions and checking for palindrome
• Space: O(N) recursion depth + result list size

🔮 Up Next

▶️ Day 39: DP + Backtracking — Palindrome Partitioning II (Min Cuts)