Palindromic Partitioning (Minimum Cuts to Split a String into Palindromes)

• Palindrome table precomputed with the boolean DP for O(1) palindrome queries on any range.
• Cut DP defines cuts[i] as the minimum cuts so the prefix s[0..i] splits entirely into palindromes.
• Recurrence is: if pal[0][i] is true, cuts[i] = 0; else cuts[i] = min over all j where pal[j][i] is true of (1 + cuts[j-1]).
• Two-layer structure means the palindrome table is the reusable building block and the cut array is a classic prefix DP.
• O(n squared) time and space for both layers combined.

What is the problem?

Given a string, find the minimum number of cuts needed so that every resulting piece is a palindrome. For "aab", one cut after the second 'a' gives ["aa", "b"], both palindromes. The answer is 1.

package com.bank.dsa;

public class PalindromicPartitioning {
    public static int minCut(String s) {
        int n = s.length();
        boolean[][] pal = new boolean[n][n];
        // Build palindrome table
        for (int i = n - 1; i >= 0; i--) {
            pal[i][i] = true;
            for (int j = i + 1; j < n; j++) {
                pal[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1]);
            }
        }
        // Cut DP
        int[] cuts = new int[n];
        for (int i = 0; i < n; i++) {
            if (pal[0][i]) {
                cuts[i] = 0;
            } else {
                cuts[i] = i; // worst case: cut before every character
                for (int j = 1; j <= i; j++) {
                    if (pal[j][i]) {
                        cuts[i] = Math.min(cuts[i], cuts[j - 1] + 1);
                    }
                }
            }
        }
        return cuts[n - 1];
    }
}

Why is this a two-layer problem?

The first layer builds the boolean palindrome table so you can query whether any range [j, i] is a palindrome in O(1). The second layer uses that table to run a prefix DP: for each position i, try every palindromic suffix ending at i and pick the one that minimizes total cuts.

package com.bank.dsa;

public class TwoLayerDemo {
    public static void main(String[] args) {
        String s = "AAB";
        int n = s.length();
        // Layer 1: palindrome table
        boolean[][] pal = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            pal[i][i] = true;
            for (int j = i + 1; j < n; j++) {
                pal[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1]);
            }
        }
        System.out.println("pal[0][1]=" + pal[0][1] + " (AA)");
        System.out.println("pal[0][2]=" + pal[0][2] + " (AAB)");
        System.out.println("pal[2][2]=" + pal[2][2] + " (B)");

        // Layer 2: cuts
        System.out.println("Min cuts: " + PalindromicPartitioning.minCut(s));
    }
}

pal[0][1]=true (AA)
pal[0][2]=false (AAB)
pal[2][2]=true (B)
Min cuts: 1

How does the cut recurrence work?

For each position i, if the entire prefix [0..i] is already a palindrome, zero cuts are needed. Otherwise, look back at every starting position j from 1 to i: if the piece [j..i] is a palindrome, the cost is 1 cut (to separate it from the prefix before j) plus the minimum cuts for the prefix [0..j-1].

package com.bank.dsa;

public class CutRecurrenceDemo {
    public static void main(String[] args) {
        String s = "ABCBA";
        System.out.println("Min cuts: " + PalindromicPartitioning.minCut(s));
        // "ABCBA" is itself a palindrome, so 0 cuts

        String s2 = "ABCD";
        System.out.println("Min cuts: " + PalindromicPartitioning.minCut(s2));
        // All distinct: 3 cuts [A,B,C,D]
    }
}

Min cuts: 0
Min cuts: 3

What are the edge cases?

A string that is already a palindrome needs 0 cuts. A single character needs 0 cuts. An empty string needs 0 cuts. A string of all distinct characters needs n-1 cuts (each character is its own palindromic piece).

package com.bank.dsa;

public class EdgeCaseDemo {
    public static void main(String[] args) {
        System.out.println(PalindromicPartitioning.minCut("ABA"));   // 0
        System.out.println(PalindromicPartitioning.minCut("A"));     // 0
        System.out.println(PalindromicPartitioning.minCut("ABCD"));  // 3
        System.out.println(PalindromicPartitioning.minCut("AABB"));  // 1 (AA, BB)
    }
}

0
0
3
1

What is the time and space complexity?

Time is O(n squared) for both the palindrome table and the cut DP. Space is O(n squared) for the palindrome table plus O(n) for the cuts array, so O(n squared) total.

How does this relate to other palindrome problems?

The palindrome table is the same building block used in the longest palindromic substring and the count of palindromic substrings. The cut DP is a separate prefix dynamic program layered on top. This composability is what makes the palindrome table so valuable.

What are common mistakes?

Forgetting to check whether the entire prefix is already a palindrome (which gives 0 cuts). Initializing cuts[i] to n instead of i (the worst case is i cuts for the prefix of length i+1). Off-by-one errors in the j-1 indexing when looking up cuts before the palindromic piece.

What are common interview follow-up questions?

• How would you return the actual partition, not just the minimum number of cuts?
• Can you optimize by computing palindromes and cuts in a single pass?
• How does this generalize to partitioning with a cost function per piece?
• What if you want to minimize the number of non-palindromic pieces instead?