Last updated on March 2nd, 2025 at 02:25 pm

Here, we see a Palindrome Partitioning II LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Dynamic Programming

Level of Question

Hard

Palindrome Partitioning II LeetCode Solution

1. Problem Statement

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.

Example 1:
Input: s = “aab”
Output: 1
Explanation: The palindrome partitioning [“aa”,”b”] could be produced using 1 cut.

Example 2:
Input: s = “a”
Output: 0

Example 3:
Input: s = “ab”
Output: 1

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Palindromic Subsequence”. This pattern involves solving problems related to palindromes, such as finding the minimum cuts required to partition a string into palindromic substrings. The solutions use techniques like dynamic programming, recursion, and backtracking to efficiently solve the problem.

3. Code Implementation in Different Languages

3.1 Palindrome Partitioning II C++

class Solution {
public:
	vector<vector<int>> dp;
	vector<vector<int>> dp1;
	bool isPalindrome(string& s, int i, int j) {
		if (i >= j) return true;
		if (dp1[i][j] != -1) return dp1[i][j];
		if (s[i] == s[j]) return dp1[i][j] = isPalindrome(s, i + 1, j - 1);
		return dp1[i][j] = false;
	}

	int solve(string s, int l, int r){
		if(l>=r) return dp[l][r] = 0;
		if(dp[l][r]!=-1) return dp[l][r];
		if(isPalindrome(s,l,r)) return dp[l][r] = 0;
		int ans = INT_MAX;
		for(int i=l;i<=r-1;i++){
			if(isPalindrome(s,l,i)) ans = min(ans, 1+solve(s,i+1,r));
		}
		return dp[l][r] = ans;
	}

	int minCut(string s) {
		dp.resize(s.size(),vector<int> (s.size(),-1));
		dp1.resize(s.size(),vector<int> (s.size(),-1));
		return solve(s,0,s.size()-1);
	}
};

3.2 Palindrome Partitioning II Java

class Solution {
public int minCut(String s) {
    char[] c = s.toCharArray();
    int n = c.length;
    int[] cut = new int[n];
    boolean[][] pal = new boolean[n][n];
    
    for(int i = 0; i < n; i++) {
        int min = i;
        for(int j = 0; j <= i; j++) {
            if(c[j] == c[i] && (j + 1 > i - 1 || pal[j + 1][i - 1])) {
                pal[j][i] = true;  
                min = j == 0 ? 0 : Math.min(min, cut[j - 1] + 1);
            }
        }
        cut[i] = min;
    }
    return cut[n - 1];
}
}

3.3 Palindrome Partitioning II JavaScript

var minCut = function(s) {
     let res = Infinity;
    const checkIfPalindrome = (str) => {
        let left = 0, right = str.length -1;
        while(left < right){
            if( str[left] != str[right]) return false;
            left ++;
            right--;
        }
        return true;
    }
    
    const compute = (str, computedResults) => {
       if(computedResults.length >= res) return;
       if(!str.length)  res = Math.min(computedResults.length, res)
       for(let g=1; g<=str.length; g++ ){
           const curString = str.slice(0, g);
           if( checkIfPalindrome(curString) ){
               compute( str.slice(g), [ ...computedResults, curString] );
           }
       }
    }
    
    compute(s, []);
    return res-1;
};

3.4 Palindrome Partitioning II Python

class Solution:
    def minCut(self, s):
        if s == s[::-1]: return 0
        lens = len(s)
        for i in range(1, lens):
            if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:
                return 1

        isPal = [[False] * (i + 1) for i in range(lens)]
        dp = range(lens) + [-1]
        for i in range(lens):
            for j in range(i, -1, -1):
                if s[i] == s[j] and (i - j < 2 or isPal[i - 1][j + 1]):
                    isPal[i][j] = True
                    dp[i] = min(dp[i], dp[j - 1] + 1)
        return dp[lens - 1]

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n3)	O(n²)
Java	O(n²)	O(n²)
JavaScript	O(2ⁿ * n)	O(n)
Python	O(n²)	O(n²)