Course4all
Join us on telegram
Home/dsa/Dynamic Programming/Palindrome Partitioning II

Palindrome Partitioning II

Master this topic with zero to advance depth.

Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Visual Representation

s = "aab" Valid partitions: ["a", "a", "b"] -> 2 cuts ["aa", "b"] -> 1 cut (Min) Result: 1
Hard

Examples

Input: s = "aab"
Output: 1

The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Input: s = "a"
Output: 0
Approach 1

Level I: Brute Force (Recursion)

Intuition

Try every possible split point for the string. If the prefix is a palindrome, recursively find the minimum cuts for the remaining suffix.

Thought Process

  1. solve(i) returns min cuts for s[i...n-1].
  2. Base case: If s[i...n-1] is a palindrome, return 0 (no more cuts needed).
  3. For each j from i to n-1:
    • If s[i...j] is a palindrome:
      • res = min(res, 1 + solve(j + 1)).
⏱ O(2^N)💾 O(N)

Detailed Dry Run

s = "aab"

  1. "a" is pal. solve("ab")
  2. "aa" is pal. solve("b") -> "b" is pal, returns 0. Total 1+0=1. Result: 1
java
public class Main {
    private static boolean isPal(String s, int i, int j) {
        while (i < j) if (s.charAt(i++) != s.charAt(j--)) return false;
        return true;
    }

    public static int solve(String s, int i) {
        if (i == s.length() || isPal(s, i, s.length() - 1)) return 0;
        int min = s.length();
        for (int j = i; j < s.length(); j++) {
            if (isPal(s, i, j)) {
                min = Math.min(min, 1 + solve(s, j + 1));
            }
        }
        return min;
    }

    public static void main(String[] args) {
        System.out.println(solve("aab", 0)); // 1
    }
}
Approach 2

Level II: Memoization (Top-Down DP)

Intuition

Cache the result of solve(i) (min cuts for suffix s[i:]) using a memo array. Also precompute palindrome check to avoid O(N) palindrome check every time.

Visual

s = "aab" memo[2] = 0 ("b" is palindrome) memo[1] = 1 ("ab" -> "a"|"b" = 1 cut, or "ab" not pal) memo[0] = 1 ("aa"|"b" = 1 cut, memo[2] cached!)
⏱ O(N^2)💾 O(N^2)

Detailed Dry Run

s="aab". solve(2)=0. solve(1)=1+solve(2)=1. solve(0): is_pal[0][1]=True -> 1+solve(2)=1. Result=1.

java
import java.util.Arrays;

public class Main {
    public static int minCut(String s) {
        int n = s.length();
        boolean[][] isPal = 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 || isPal[i+1][j-1]))
                    isPal[i][j] = true;

        int[] memo = new int[n];
        Arrays.fill(memo, -1);
        return solve(s, isPal, memo, 0);
    }

    static int solve(String s, boolean[][] isPal, int[] memo, int i) {
        if (i == s.length() || isPal[i][s.length()-1]) return 0;
        if (memo[i] != -1) return memo[i];
        int min = s.length();
        for (int j = i; j < s.length(); j++)
            if (isPal[i][j]) min = Math.min(min, 1 + solve(s, isPal, memo, j+1));
        return memo[i] = min;
    }

    public static void main(String[] args) {
        System.out.println(minCut("aab")); // 1
    }
}
Approach 3

Level III: Dynamic Programming (Two Passes)

Intuition

We need two DP arrays. One 2D array isPal[i][j] to precompute if s[i...j] is a palindrome. Another 1D array cuts[i] to store the minimum cuts needed for s[0...i].

Thought Process

  1. Precompute isPal[i][j] using standard palindrome DP: s[i] == s[j] && (j-i < 2 || isPal[i+1][j-1]).
  2. Initialize cuts[i] = i (max possible cuts: each char separate).
  3. For j from 0 to n-1:
    • If isPal[0][j] is true, cuts[j] = 0 (no cuts needed for entire prefix).
    • Else, for i from 1 to j:
      • If isPal[i][j] is true, cuts[j] = min(cuts[j], cuts[i-1] + 1).
⏱ O(N^2)💾 O(N^2)

Detailed Dry Run

s = "aab" Precomputed isPal: [0,0]=T, [1,1]=T, [2,2]=T, [0,1]=T ("aa")

jisPal(0,j)Actioncuts[j]
0T0 cuts0
1T0 cuts0
2Fcuts[1]+1 ("aa""b")
Result: 1
java
public class Main {
    public static int minCut(String s) {
        int n = s.length();
        boolean[][] isPal = 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 || isPal[i + 1][j - 1])) {
                    isPal[i][j] = true;
                }
            }
        }

        int[] cuts = new int[n];
        for (int j = 0; j < n; j++) {
            if (isPal[0][j]) {
                cuts[j] = 0;
            } else {
                cuts[j] = j;
                for (int i = 1; i <= j; i++) {
                    if (isPal[i][j]) cuts[j] = Math.min(cuts[j], cuts[i - 1] + 1);
                }
            }
        }
        return cuts[n - 1];
    }

    public static void main(String[] args) {
        System.out.println(minCut("aab")); // 1
    }
}
← Previous QuestionMaximal Square
Next Question →Interleaving String