# Solution For Palindrome Partitioning Ii

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

Constraints:

1 <= s.length <= 2000
s consists of lower-case English letters only.

Solution:

Approach:

The problem requires us to find the minimum number of cuts required to partition a string s into palindromic substrings. This can be done by using Dynamic Programming.

We can use the following approach to solve this problem:

Step 1: Initialize a one-dimensional DP array dp of size n + 1, where n is the length of the string. Here dp[i] will store the minimum number of cuts required to partition the string s[0..i-1] into palindromic substrings.

Step 2: Initialize each element of the array as its index value.

Step 3: Traverse the array from the second character to the end of the string.

Step 4: For each character i, traverse the array from the start to i.

Step 5: If the current substring s[j..i] is a palindrome, update the minimum cuts required to partition the string s[0..i-1].

The minimum cuts required will be dp[j] + 1, where dp[j] is the minimum number of cuts required to partition the string s[0..j-1] into palindromic substrings, and the additional cut 1 is made to include the current palindrome string s[j..i]. We take minimum of all such values as we want the minimum number of cuts possible.

Step 6: Return dp[n] – 1, as we’re working on 0-based indexing and this will be the final answer.

Code:

The code implementation of the above approach is given below:

class Solution {
public:
int minCut(string s) {
int n = s.length();

``````    vector<int> dp(n + 1, 0);
for(int i = 0;i <= n;i++)
dp[i] = i - 1;

for(int i = 1;i < n;i++) {
for(int j = 0;j <= i;j++) {
if(isPalindrome(s, j, i)) {
dp[i + 1] = min(dp[i + 1], dp[j] + 1);
}
}
}
return dp[n];
}
``````

private:
bool isPalindrome(string s, int i, int j) {
while(i < j) {
if(s[i] != s[j])
return false;
i++;
j–;
}
return true;
}
};

Time Complexity:

The time complexity of the solution is O(n^2) as we’re traversing two loops for i and j, and checking palindrome string takes O(n).

Space Complexity:

The space complexity of the solution is O(n), as we’re using a dp array of size n.

## Step by Step Implementation For Palindrome Partitioning Ii

```public class Solution {
public int minCut(String s) {
//check null
if(s == null || s.length() == 0){
return 0;
}
//get length
int len = s.length();
//create an array to store whether the string from ith to jth is palindrome
boolean[][] dp = new boolean[len][len];
//create an array to store the minCut from ith to jth
int[] cut = new int[len];

for(int j = 0; j < len; j++){
cut[j] = j; //set the max # of cut as j
for(int i = 0; i <= j; i++){
if(s.charAt(i) == s.charAt(j) && (j-i <= 1 || dp[i+1][j-1])){
dp[i][j] = true;
//if need to cut, add 1
if(i > 0){
cut[j] = Math.min(cut[j], cut[i-1] + 1);
}else{
//if [0...j] is palindrome, no need to cut
cut[j] = 0;
}
}
}
}
return cut[len-1];
}
}```
```def minCut(self, s):
if s is None or len(s) == 0:
return 0
n = len(s)
is_palindrome = [[False for i in range(n)] for j in range(n)]
for i in range(n):
is_palindrome[i][i] = True
for i in range(n-1):
is_palindrome[i][i+1] = (s[i] == s[i+1])
for length in range(2, n):
for start in range(n-length):
is_palindrome[start][start+length] = is_palindrome[start+1][start+length-1] and s[start] == s[start+length]
cuts = [i-1 for i in range(n+1)]
for i in range(n):
for j in range(i, -1, -1):
if is_palindrome[j][i]:
cuts[i+1] = min(cuts[i+1], cuts[j] + 1)
return cuts[n]```
```var minCut = function(s) {
let n = s.length;
let cut = Array(n).fill(0);
let isPal = Array(n).fill(Array(n).fill(false));

for (let j = 0; j < n; j++) {
cut[j] = j; // set maximum # of cuts to be j
for (let i = 0; i <= j; i++) {
if (s[i] == s[j] && (j - i <= 1 || isPal[i+1][j-1])) {
isPal[i][j] = true;
// if [i,j] is a palindrome, no need to cut
if (i == 0) {
cut[j] = 0;
} else {
cut[j] = Math.min(cut[j], cut[i-1] + 1);
}
}
}
}

return cut[n-1];
};```
```class Solution {
public:
int minCut(string s) {
int n = s.size();
vector cut(n+1, 0);  // number of cuts for the first k characters
for (int i = 0; i <= n; i++) cut[i] = i-1;
for (int i = 0; i < n; i++) {
for (int j = 0; i-j >= 0 && i+j < n && s[i-j]==s[i+j] ; j++) // odd length palindrome
cut[i+j+1] = min(cut[i+j+1],1+cut[i-j]);

for (int j = 1; i-j+1 >= 0 && i+j < n && s[i-j+1]==s[i+j]; j++) // even length palindrome
cut[i+j+1] = min(cut[i+j+1],1+cut[i-j+1]);
}
return cut[n];
}
};```
```public class Solution {
public int MinCut(string s) {
if (string.IsNullOrEmpty(s)) return 0;
int n = s.Length;
// dp[i,j] represents the min cut needed for substring s[i...j]
int[,] dp = new int[n,n];
// isPal[i,j] represents whether substring s[i...j] is a palindrome
bool[,] isPal = new bool[n,n];
for (int j = 0; j < n; j++) {
dp[j,j] = 0;
isPal[j,j] = true;
for (int i = j-1; i >= 0; i--) {
if (s[i] == s[j] && (j-i < 2 || isPal[i+1,j-1])) {
isPal[i,j] = true;
dp[i,j] = 0;
} else {
isPal[i,j] = false;
dp[i,j] = int.MaxValue;
for (int k = i; k < j; k++) {
dp[i,j] = Math.Min(dp[i,j], dp[i,k]+dp[k+1,j]+1);
}
}
}
}
return dp[0,n-1];
}
}```
Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]