## Algorithm

Problem Name: 132. Palindrome Partitioning II

Given a string `s`, partition `s` such that every substringof 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 lowercase English letters only.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int _min(int a, int b) {
return a < b ? a : b;
}
int minCut(char* s) {
int *dp, n, i, k;

n = strlen(s);

dp = malloc((n + 1) * sizeof(int));     // number of cuts on length
//assert(dp);

dp[0] = -1;
for (i = 0; i  <  n; i ++) {
dp[i + 1] = dp[i] + 1;
}

for (i = 0; i  <  n; i ++) {
dp[i + 1] = _min(dp[i + 1], dp[i] + 1);

for (k = 1;                 // "aba"
i - k >= 0 &&
i + k  <  n &&
s[i - k] == s[i + k];
k ++) {
dp[i + k + 1] = _min(dp[i + k + 1], dp[i - k] + 1);
}

for (k = 1;                 // "aaaa"
i - k + 1 >= 0 &&
i + k  <  n &&
s[i - k + 1] == s[i + k];
k ++) {
dp[i + k + 1] = _min(dp[i + k + 1], dp[i - k + 1] + 1);
}
}

i = dp[n];

free(dp);

return i;
}
``````
Copy The Code &

Input

cmd
s = "aab"

Output

cmd
1

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <iostream>
#include <string>
#include <vector>
#include <cassert>

using namespace std;

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

vector<int> dp(n);
vector < vector<int> > mem(n, vector<int>(n)); // memorization for palindrome

int i, j, k;
// build palindrome table
for (i = 0; i  <  n; i++) {
mem[i][i] = 1;
j = i, k = i + 1; // even length
while(j >= 0 && k  < = n - 1) {
if (s[j] != s[k]) break;
mem[j][k] = 1;
j--;
k++;
}
j = i - 1, k = i + 1; // odd length
while(j >= 0 && k  < = n - 1) {
if (s[j] != s[k]) break;
mem[j][k] = 1;
j--;
k++;
}
}

// run dynamic programming
dp[0] = 0;
for (i = 1; i  <  n; i++) {
if (mem[0][i]) {
dp[i] = 0;
}
else {
int min = dp[i - 1] + 1;
for (j = 0; j  <  i; j++) {
if (mem[j + 1][i] && dp[j] + 1 < min) {// if right half is palindrome
min = dp[j] + 1;
}
}
dp[i] = min;
}
}

return dp[n - 1];
}
};

int main() {
string str0 = "aababa";
string str1 = "ababa";

Solution s;

assert(s.minCut(str0) == 1);
assert(s.minCut(str1) == 0);

printf("all tests passed!\n");

return 0;
}
``````
Copy The Code &

Input

cmd
s = "aab"

Output

cmd
1

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const minCut = function(s) {
const n = s.length
if (n <= 1) return 0
const dp = new Array(n).fill(0)
for (let i = 1; i  <  n; i++) dp[i] = i
for (let i = 1; i  <  n; i++) {
// odd
for (
let start = i, end = i;
end  <  n && start >= 0 && s[end] === s[start];
start--, end++
) {

dp[end] = Math.min(dp[end], start === 0 ? 0 : dp[start - 1] + 1)
}
// even
for (
let start = i - 1, end = i;
end  <  n && start >= 0 && s[end] === s[start];
start--, end++
) {
dp[end] = Math.min(dp[end], start === 0 ? 0 : dp[start - 1] + 1)
}
}
return dp[n - 1]
}``````
Copy The Code &

Input

cmd
s = "a"

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def minCut(self, s):
q, pal, used = [(0, 0)], collections.defaultdict(list), {(0, 0)}
for i in range(len(s)):
for j in range(i, len(s)):
if s[i:j + 1] == s[i:j + 1][::-1]: pal[i].append(j + 1)
while q:
cuts, i = heapq.heappop(q)
i *= -1
if i == len(s): return cuts - 1
for j in pal[i]:
if (cuts + 1, -j) not in used: