☕ DSA Java Articles

Topics › Dynamic Programming › MCM DP - Partition DP

Palindrome Partitioning (MCM Variation)

Hard TUF ID 2854 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given a string s, cut it into pieces so that every piece is a palindrome (reads the same forwards and backwards). Return the minimum number of cuts needed. A string that is already a palindrome needs 0 cuts.

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

Example 1

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

Example 2

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

Every single character is a palindrome, so a solution always exists and the answer is at most n - 1.

Why it is called an MCM variation

Matrix Chain Multiplication asks for the best place to split a range [i, j], then solves both halves recursively. The same template works here:

cuts(i, j) = 0                                         if s[i..j] is a palindrome
cuts(i, j) = min over k in [i, j - 1] of  cuts(i, k) + 1 + cuts(k + 1, j)

That is correct, but it has O(n^2) states and O(n) split points each, so O(n^3) time even with memoisation, plus the palindrome checks. For n = 2000 that is billions of steps.

The key observation is that we never need to split the left side again. In any valid partition, the first piece s[0..j] is itself a palindrome. So instead of “split anywhere and solve both sides”, say “choose the first palindromic piece, then solve the rest”. The left side is finished the moment we choose it. The state shrinks from a range (i, j) to a single starting index i; this is often called front partitioning. We count pieces rather than cuts, because the count of pieces composes cleanly (1 + pieces of the rest), and convert at the end: cuts = pieces - 1.

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

Approach 1: Recursion

Intuition. From index i, try every end j such that s[i..j] is a palindrome, recurse on j + 1, and keep the best. j = i (a single character) always qualifies, so the minimum always exists.

Algorithm.

  1. If i == n, return 0 (no characters, no pieces).
  2. For each j from i to n - 1: if s[i..j] is a palindrome, candidate 1 + pieces(j + 1).
  3. Return the minimum candidate.
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 recursion(String s) {
    return pieces(0, s) - 1;                                  // cuts = pieces - 1
}

static int pieces(int i, String s) {                          // fewest palindromic pieces for s[i..]
    if (i == s.length()) return 0;
    int best = Integer.MAX_VALUE;
    for (int j = i; j < s.length(); j++) {
        if (isPalindrome(s, i, j)) best = Math.min(best, 1 + pieces(j + 1, s));
    }
    return best;
}

Complexity. Exponential time: for a string like "aaaa...a" every prefix is a palindrome, and the recursion visits all 2^(n - 1) partitions. Space O(n) for the stack.

Approach 2: Memoization

Intuition. pieces(i) depends only on i, so there are just n distinct states. After "aa" | ... and "a" | "a" | ... the rest of the problem is identical; cache it.

Algorithm. Same recursion with dp[i] initialised to -1, filled on first computation.

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) in the worst case: n states, up to n ends each, and the palindrome check costs up to O(n). In practice the check usually stops at the first mismatch, so random strings run much faster. Space O(n) for the table and the stack.

Approach 3: Tabulation

Intuition. pieces(i) reads only pieces(j + 1) with j + 1 > i, so fill dp from right to left. dp[n] = 0 is the base case.

Algorithm.

  1. dp[n] = 0.
  2. For i from n - 1 down to 0: dp[i] = min(1 + dp[j + 1]) over every j ≥ i with s[i..j] a palindrome.
  3. Return dp[0] - 1.
static int tabulation(String s) {
    int n = s.length();
    int[] dp = new int[n + 1];                                // dp[i]: fewest pieces for s[i..n-1]; dp[n] = 0
    for (int i = n - 1; i >= 0; i--) {
        int best = Integer.MAX_VALUE;
        for (int j = i; j < n; j++) {
            if (isPalindrome(s, i, j)) best = Math.min(best, 1 + dp[j + 1]);
        }
        dp[i] = best;
    }
    return dp[0] - 1;
}

Dry run on "aab":

i palindromic pieces starting at i dp[i]
3 (end of string) 0
2 “b” → 1 + dp[3] = 1 1
1 “a” → 1 + dp[2] = 2 (“ab” is not a palindrome) 2
0 “a” → 1 + dp[1] = 3, “aa” → 1 + dp[2] = 2 (“aab” is not) 2

Answer dp[0] - 1 = 1.

Complexity. Time O(n^3) worst case, for the same reason as memoisation. Space O(n).

Approach 4: Optimal, palindrome table built on the fly

Intuition. The only expensive part left is the O(n) palindrome test. A substring s[i..j] is a palindrome exactly when its two ends match and the inside s[i+1..j-1] is a palindrome (or has length 0 or 1). That is itself a tiny DP: pal[i][j] depends on pal[i + 1][j - 1]. Since we already process i from right to left, row i + 1 of pal is complete when we reach row i, so we can fill pal inside the same double loop and test each substring in O(1).

Algorithm.

  1. Allocate pal[n][n] and dp[n + 1] with dp[n] = 0.
  2. For i from n - 1 down to 0, for j from i to n - 1:
    • If s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1]), mark pal[i][j] and consider 1 + dp[j + 1].
  3. Store the minimum in dp[i]; return dp[0] - 1.
static int optimal(String s) {
    int n = s.length();
    boolean[][] pal = new boolean[n][n];                      // pal[i][j]: s[i..j] is a palindrome
    int[] dp = new int[n + 1];
    for (int i = n - 1; i >= 0; i--) {
        int best = Integer.MAX_VALUE;
        for (int j = i; j < n; j++) {
            // ends match and the inside is empty, one character, or already known to be a palindrome
            if (s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1])) {
                pal[i][j] = true;
                best = Math.min(best, 1 + dp[j + 1]);
            }
        }
        dp[i] = best;
    }
    return dp[0] - 1;
}

Complexity. Time O(n^2): each (i, j) pair is handled in constant time. Space O(n^2) for pal. For n = 2000 that is 4 million booleans (about 4 MB), which is fine.

There is also an O(n) space alternative that expands around every centre and updates a cut array, but the table version above is the one to know: it is the general technique for “is this substring a palindrome” queries in any DP.

Edge cases and pitfalls