Dynamic Programming • Front Partitioning

Palindrome Partitioning

Find the minimum number of cuts needed to partition a string such that every substring is a palindrome.

Overview

This falls under the "Front Partitioning" pattern. We want to find the optimal way to partition a prefix `s[0...i]`, using answers from smaller prefixes `s[0...j-1]`.

Fast Palindrome Check

Instead of an O(N) check every time, we build a 2D boolean DP `isPal[j][i]` dynamically. `s[j...i]` is a palindrome if `s[j]==s[i]` AND `s[j+1...i-1]` is a palindrome.

The Cut Logic

If `s[j...i]` is a palindrome, we can make a cut right before `j`. The total cuts would be `1 + dp[j-1]` (the min cuts for the prefix ending at `j-1`).

Base Case Bypass

If `j == 0`, the entire substring `s[0...i]` is a palindrome. This means NO cuts are needed! So we set `minCuts = 0`.

a

b

DP Array (Min Cuts)

-

Code Tracker

:::

1let dp = Array(n).fill(0);

2let isPal = Array.from({length: n}, () => Array(n).fill(false));

3for (let i = 0; i < n; i++) {

4 let minCuts = i;

5 for (let j = 0; j <= i; j++) {

6 if (s[j] === s[i] && (i - j <= 2 || isPal[j+1][i-1])) {

7 isPal[j][i] = true;

8 if (j === 0) minCuts = 0;

9 else minCuts = Math.min(minCuts, dp[j-1] + 1);

10 }

11 }

12 dp[i] = minCuts;

13}

14return dp[n-1];