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

🧠 Concept Deep Dive

Given a string s, partition it such that every substring is a palindrome, and return the minimum number of cuts needed to make that happen.

Unlike Day 38 where we returned all valid partitions, this time we want the fewest cuts to create only palindromic substrings.

We use DP for memoizing palindromic substrings and compute the minimum cuts dynamically.

🎯 Visual Intuition

For s = "aab", the best way to split is:

"aa" | "b"

So, only 1 cut is needed.

We use cut[i] to store the min number of cuts needed for substring s[0..i].

🛠️ Code Pattern: Dynamic Programming + Palindrome Check

function minCut(s: string): number {
  const n = s.length;
  const cut = Array(n).fill(0);
  const isPal = Array.from({ length: n }, () => Array(n).fill(false));

  for (let i = 0; i < n; i++) {
    let min = i;
    for (let j = 0; j <= i; j++) {
      if (s[i] === s[j] && (i - j <= 1 || isPal[j + 1][i - 1])) {
        isPal[j][i] = true;
        min = j === 0 ? 0 : Math.min(min, cut[j - 1] + 1);
      }
    }
    cut[i] = min;
  }

  return cut[n - 1];
}

📘 Example

Input: "aab"
Output: 1

Input: "a"
Output: 0

Input: "abccbc"
Output: 2
// One optimal split: "a | bccb | c"

🧪 Homework

1. Try implementing it with a recursive + memoization approach.
2. Can you print the actual cut partitions?
3. What if all characters are the same?

🧠 Big-O Cheat Sheet

• Time: O(N^2) — double loop for substring checking
• Space: O(N^2) for palindrome memo table

🔮 Up Next

▶️ Day 40: Hard DP — Burst Balloons Problem