☕ DSA Java Articles

Topics › Dynamic Programming › MCM DP - Partition DP

Palindrome partitioning II

Hard TUF ID 329 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given a string s, cut it into pieces so that every piece is a palindrome (it reads the same forwards and backwards). Return the minimum number of cuts needed. A string that is already a palindrome needs 0 cuts. Since a single character is always a palindrome, a string of length n never needs more than n - 1 cuts.

Constraints (LeetCode 132): 1 ≤ n ≤ 2000, lowercase English letters only.

Example 1

s = "aab"
answer = 1               // "aa" | "b"

Example 2

s = "bababcbadcede"
answer = 4               // "bab" | "abcba" | "d" | "c" | "ede"

Example 3

s = "aaba"
answer = 1               // "a" | "aba"

Example 3 is a warning against greed. The longest palindrome at the front is "aa", but taking it leaves "ba", which needs one more cut, for 2 in total. Starting with the shorter "a" lets the rest be the single palindrome "aba".

Front partition: why one index is enough

This problem sits in the partition DP family, so the first instinct is the matrix chain shape: f(i, j) for every substring, trying every split point k. That works, but it has O(n^2) states with O(n) splits each, plus palindrome checks, which is too slow for n = 2000. It is also more than we need.

Read the partition from left to right instead. Any valid partition has a first piece s[i..j], which must be a palindrome. Once that piece is chosen, the rest of the string, s[j+1..], is a smaller instance of exactly the same problem, and it does not care how we reached it. So the only information a state needs is where the remaining suffix starts:

f(n) = 0                                              (empty suffix: zero pieces)
f(i) = 1 + min over j in [i, n - 1] with s[i..j] a palindrome of f(j + 1)
answer = f(0) - 1

f counts pieces, not cuts. k pieces always need k - 1 cuts, hence the final - 1. Striver’s version writes the same thing by charging a cut after every piece, including a pretend cut after the last one, and removes that extra cut at the end. The minimum always exists because j = i is always allowed: one character is a palindrome.

Why is this correct? Take any optimal partition of the suffix starting at i. Its first piece is one of the palindromes we try. The pieces after it form a partition of s[j+1..], and that partition must itself be optimal, otherwise swapping in a better one would improve the whole. So trying every palindromic first piece and adding the best answer for the remainder finds the optimum. This is the “front partition” pattern: one index, one loop over the length of the first piece.

Approach 1: Recursion

Intuition. Implement f directly. At position i, try every end j; whenever s[i..j] is a palindrome, recurse on j + 1 and keep the smallest result. A two-pointer helper checks a palindrome by walking inward from both ends.

Algorithm.

  1. If i == n, return 0 pieces.
  2. For each j from i to n - 1: if s[i..j] is a palindrome, candidate = 1 + f(j + 1).
  3. Return the minimum candidate. The caller subtracts 1 to turn pieces into cuts.
static boolean isPalindrome(String s, int i, int j) {
    while (i < j) if (s.charAt(i++) != s.charAt(j--)) return false;
    return true;
}

static int recursive(String s) {
    return solve(0, s) - 1;                                 // k pieces need k - 1 cuts
}

static int solve(int i, String s) {
    if (i == s.length()) return 0;                          // nothing left: zero pieces
    int best = Integer.MAX_VALUE;
    for (int j = i; j < s.length(); j++) {
        if (isPalindrome(s, i, j)) best = Math.min(best, 1 + solve(j + 1, s));
    }
    return best;
}

Complexity. Time exponential. On "aaaa...a" every one of the 2^(n-1) ways to cut the string is valid, and without caching f(i) is recomputed so often that the number of calls doubles with each extra character. Each call also spends up to O(n^2) on palindrome checks. Space O(n) for the recursion depth.

Approach 2: Memoization

Intuition. There are only n + 1 different suffixes, so there are only n + 1 different values of f. Store each one in dp[i] the first time it is computed. Piece counts are positive, so -1 safely means “not computed yet”.

Algorithm.

  1. Fill dp with -1.
  2. Run the same recursion, returning dp[i] when it is already known and storing every new result.
  3. Return dp[0] - 1.
static int memoization(String s) {
    int[] dp = new int[s.length()];
    Arrays.fill(dp, -1);
    return memo(0, s, dp) - 1;
}

static int memo(int i, String s, int[] dp) {
    if (i == s.length()) return 0;
    if (dp[i] != -1) return dp[i];
    int best = Integer.MAX_VALUE;
    for (int j = i; j < s.length(); j++) {
        if (isPalindrome(s, i, j)) best = Math.min(best, 1 + memo(j + 1, s, dp));
    }
    return dp[i] = best;
}

Complexity. Time O(n^3): n states, up to n choices of j each, and an O(n) palindrome check per choice. Space O(n) for dp plus O(n) stack. On random strings most checks fail after a character or two, but on a string of 2000 identical letters every check runs to the middle, which is several hundred million comparisons.

Approach 3: Tabulation

Intuition. f(i) only reads f(j + 1) with j + 1 > i. So if we fill dp from the right end towards the left, every value we need is already in the table. dp[n] = 0 is the default value of a fresh Java array.

Algorithm.

  1. Allocate dp of size n + 1.
  2. For i from n - 1 down to 0: dp[i] = min(1 + dp[j + 1]) over palindromic s[i..j].
  3. Return dp[0] - 1.
static int tabulation(String s) {
    int n = s.length();
    int[] dp = new int[n + 1];                              // dp[n] = 0
    for (int i = n - 1; i >= 0; i--) {
        dp[i] = Integer.MAX_VALUE;
        for (int j = i; j < n; j++) {
            if (isPalindrome(s, i, j)) dp[i] = Math.min(dp[i], 1 + dp[j + 1]);
        }
    }
    return dp[0] - 1;
}

Complexity. Time O(n^3) for the same reason as memoization, space O(n), and no recursion.

Approach 4: Optimal, palindrome table built on the fly

Intuition. The DP itself is only O(n^2) work; the extra factor of n comes entirely from isPalindrome. Palindromes have a recursive structure we can exploit: s[i..j] is a palindrome exactly when s[i] == s[j] and the inside s[i+1..j-1] is a palindrome (or the piece has length 1 or 2, so the inside is empty).

The inside starts at i + 1. Because the outer loop moves i downward, row i + 1 of a boolean table pal was completed in the previous iteration. So we can decide pal[i][j] in O(1) at the exact moment the DP needs it, inside the same double loop. No separate preprocessing pass is needed.

Algorithm.

  1. For i from n - 1 down to 0, and j from i to n - 1:
  2. If s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1]), mark pal[i][j] = true and relax dp[i] with 1 + dp[j + 1].
  3. Return dp[0] - 1.
static int optimal(String s) {
    int n = s.length();
    boolean[][] pal = new boolean[n][n];
    int[] dp = new int[n + 1];                              // dp[n] = 0
    for (int i = n - 1; i >= 0; i--) {
        dp[i] = Integer.MAX_VALUE;
        for (int j = i; j < n; j++) {
            if (s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1])) {
                pal[i][j] = true;                           // row i + 1 was filled one iteration earlier
                dp[i] = Math.min(dp[i], 1 + dp[j + 1]);
            }
        }
    }
    return dp[0] - 1;
}

Dry run on Example 3, s = "aaba":

i palindromic first pieces s[i..j] candidates 1 + dp[j + 1] dp[i]
4 (empty suffix)   0
3 “a” 1 + 0 1
2 “b” 1 + 1 2
1 “a”, “aba” 1 + 2, 1 + 0 1
0 “a”, “aa” 1 + 1, 1 + 2 2

dp[0] = 2 pieces, so 1 cut. At i = 0 the longer piece "aa" gives 3 pieces, while the short piece "a" hands over to dp[1] = 1, which is the palindrome "aba". The DP finds this because it tries every first piece rather than the longest.

Complexity. Time O(n^2): each pair (i, j) is handled in constant time. Space O(n^2) for the boolean table, about 4 MB for n = 2000, plus O(n) for dp.

Edge cases and pitfalls