Skip to main content
Interval DP

Min Palindrome Partitions

Minimum cuts to split a string into palindromic parts. dp[i] = min cuts for s[0..i]. For each i, try every j ≤ i: if s[j..i] is a palindrome, dp[i] = min(dp[i], dp[j−1] + 1). Precompute which substrings are palindromes.

O(n²)
·
O(n²)

How It Works

Minimum palindrome partitioning combines two DP layers. First, precompute a boolean table isPal[j][i] telling whether s[j..i] is a palindrome, using the expansion recurrence isPal[j][i] = (s[j] == s[i]) and isPal[j+1][i-1], filled by increasing length in O(n^2). Second, define cuts[i] as the minimum cuts for the prefix ending at i: for every j <= i where s[j..i] is a palindrome, cuts[i] = min(cuts[i], cuts[j-1] + 1), and zero if the whole prefix is already a palindrome.

Without the precomputed table, each palindrome check costs O(n) and the total climbs to O(n^3); with it, the whole algorithm is O(n^2) time and O(n^2) space. The layered structure — one table answering yes/no queries, another optimizing over them — recurs across many string DP problems.

Step-by-Step Visualization

Min cuts to partition 'aab' into palindromes
a
0
a
1
b
2
dp[0, 0, 1]
1/3

Code

Java
static int minCut(String s) {
  int n = s.length();
  int[] dp = new int[n];
  for (int i = 0; i < n; i++) dp[i] = i;
  boolean[][] isPalin = new boolean[n][n];

  for (int j = 0; j < n; j++)
    for (int i = 0; i <= j; i++)
      if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || isPalin[i+1][j-1])) {
        isPalin[i][j] = true;
        dp[j] = i == 0 ? 0 : Math.min(dp[j], dp[i-1] + 1);
      }
  return dp[n-1];
}

Tips & Gotchas

1dp[i] = min cuts to partition s[0..i] into palindromes
2Pre-compute isPalin[i][j] for O(1) palindrome checks
3If s[0..i] itself is a palindrome, dp[i] = 0

Practice Problems

  • 1Palindrome Partitioning II
  • 2Palindrome Partitioning
  • 3Palindromic Substrings
  • 4Longest Palindromic Substring

About the Interval DP Pattern

Solve subproblems on every contiguous range [i..j]. The outer loop iterates over range lengths, the inner loops over starting positions. At each range, try every possible split point to find the optimum.

Key insight

The framework: 1) Define state (what changes between subproblems). 2) Write recurrence relation. 3) Identify base cases. 4) Decide iteration order. Most DP is either 1D, 2D, or interval-based.

Common Dynamic Programming Interview Problems

  • Climbing Stairs
  • Coin Change
  • Longest Common Subsequence
  • 0/1 Knapsack
  • Edit Distance
  • House Robber
  • Longest Increasing Subsequence
  • Word Break

Frequently Asked Questions

How is this different from Palindrome Partitioning I?

Partitioning I enumerates all valid palindromic partitions via backtracking, so its output — and runtime — can be exponential. Partitioning II asks only for the minimum number of cuts, a single optimal value, which is exactly what DP computes in polynomial time.

Why precompute the palindrome table instead of checking on the fly?

Each on-the-fly two-pointer check costs O(n), and it sits inside an O(n^2) double loop, giving O(n^3) overall. The DP table answers every 'is s[j..i] a palindrome' query in O(1) after one O(n^2) preprocessing pass.

What are the base cases for the cuts array?

cuts[i] = 0 whenever s[0..i] is itself a palindrome, since no cut is needed. Otherwise initialize cuts[i] to i (worst case: cut between every character) and improve it with cuts[j-1] + 1 for each palindromic suffix s[j..i].