Back to DSA

Palindrome Partitioning II

hard
Acceptance: 36%
Dynamic Programming

Given a string, find the fewest number of cuts required to partition it so that every resulting piece reads the same forwards and backwards.

Examples

Example 1:
Input:s = "abcba"
Output:0
Explanation: The entire string is already a palindrome, so no cuts are needed.
Example 2:
Input:s = "abcdef"
Output:5
Explanation: Each character must be its own partition, requiring 5 cuts.

Hints

Related Problems

House RobbermediumClimbing StairseasyLongest Increasing SubsequencemediumWord BreakmediumEdit Distancehard
00:00
class Solution {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] isPalin = new boolean[n][n];
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = i;
            for (int j = 0; j <= i; j++) {
                if (s.charAt(i) == s.charAt(j) && (i - j <= 2 || isPalin[j + 1][i - 1])) {
                    isPalin[j][i] = true;
                    dp[i] = (j == 0) ? 0 : Math.min(dp[i], dp[j - 1] + 1);
                }
            }
        }
        return dp[n - 1];
    }
}
Time complexityO(n^2)
Space complexityO(n^2)