Problem Statement: Palindrome Partitioning II
Given a string s, you need to partition it such that every substring of the partition is a palindrome. Return the minimum number of cuts required to partition s such that every substring is a palindrome.
Example
Example 1:
Input: s = "aab" Output: 1
Explanation: The palindrome partitioning [“aa”, “b”] could be made with 1 cut.
Example 2:
Input: s = "a" Output: 0
Explanation: The string is already a palindrome, so no cuts are needed.
Example 3:
Input: s = "abac" Output: 1
Explanation: The palindrome partitioning [“aba”, “c”] could be made with 1 cut.
Approach and Algorithm
- Dynamic Programming (DP):
- We will use two dynamic programming tables:
dp[i]: Represents the minimum number of cuts needed for the substrings[0...i].palindrome[i][j]: A 2D table wherepalindrome[i][j]isTrueifs[i...j]is a palindrome, otherwiseFalse.
- We will use two dynamic programming tables:
- Filling
palindrome[][]:- A single character is always a palindrome (
palindrome[i][i] = True). - A two-character substring is a palindrome if both characters are the same.
- For substrings of length greater than 2,
s[i...j]is a palindrome ifs[i] == s[j]andpalindrome[i+1][j-1]is also a palindrome.
- A single character is always a palindrome (
- Filling
dp[]:- Start with
dp[i] = i(maximum cuts required: cut each character). - For each index
i, iterate over all possible previous indicesj, ifs[j+1...i]is a palindrome, then updatedp[i] = min(dp[i], dp[j] + 1).
- Start with
- Time Complexity:
- Constructing the
palindrome[][]table takes O(n^2). - Filling the
dp[]table also takes O(n^2). - Thus, the overall time complexity is O(n^2), where
nis the length of the string.
- Constructing the
- Space Complexity:
- The space complexity is O(n^2) due to the
palindrome[][]table.
- The space complexity is O(n^2) due to the
Code in Multiple Languages
C
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define MAX 1000
int minCut(char* s) {
int n = strlen(s);
bool palindrome[n][n];
int dp[n+1];
for (int i = 0; i <= n; i++) dp[i] = i - 1;
memset(palindrome, 0, sizeof(palindrome));
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
palindrome[i][j] = (s[i] == s[j]) && (j - i <= 2 || palindrome[i + 1][j - 1]);
}
}
for (int i = 0; i < n; i++) {
if (palindrome[0][i]) dp[i] = 0;
else {
for (int j = 0; j < i; j++) {
if (palindrome[j + 1][i]) dp[i] = (dp[i] < dp[j] + 1) ? dp[i] : dp[j] + 1;
}
}
}
return dp[n - 1];
}
int main() {
char s[] = "aab";
printf("%d\n", minCut(s));
return 0;
}
C++
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int minCut(string s) {
int n = s.length();
vector<vector<bool>> palindrome(n, vector<bool>(n, false));
vector<int> dp(n + 1, n);
dp[0] = -1; // no cut needed for empty string
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
palindrome[i][j] = (s[i] == s[j]) && (j - i <= 2 || palindrome[i + 1][j - 1]);
}
}
for (int i = 0; i < n; i++) {
if (palindrome[0][i]) dp[i] = 0;
else {
for (int j = 0; j < i; j++) {
if (palindrome[j + 1][i]) dp[i] = min(dp[i], dp[j] + 1);
}
}
}
return dp[n - 1];
}
int main() {
string s = "aab";
cout << minCut(s) << endl;
return 0;
}
Java
public class PalindromePartitioning {
public static int minCut(String s) {
int n = s.length();
boolean[][] palindrome = new boolean[n][n];
int[] dp = new int[n + 1];
for (int i = 0; i <= n; i++) dp[i] = i - 1;
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
palindrome[i][j] = (s.charAt(i) == s.charAt(j)) && (j - i <= 2 || palindrome[i + 1][j - 1]);
}
}
for (int i = 0; i < n; i++) {
if (palindrome[0][i]) dp[i] = 0;
else {
for (int j = 0; j < i; j++) {
if (palindrome[j + 1][i]) dp[i] = Math.min(dp[i], dp[j] + 1);
}
}
}
return dp[n - 1];
}
public static void main(String[] args) {
String s = "aab";
System.out.println(minCut(s));
}
}
Python
def minCut(s: str) -> int:
n = len(s)
palindrome = [[False] * n for _ in range(n)]
dp = [i for i in range(-1, n)]
for i in range(n - 1, -1, -1):
for j in range(i, n):
palindrome[i][j] = (s[i] == s[j]) and (j - i <= 2 or palindrome[i + 1][j - 1])
for i in range(n):
if palindrome[0][i]:
dp[i] = 0
else:
for j in range(i):
if palindrome[j + 1][i]:
dp[i] = min(dp[i], dp[j] + 1)
return dp[n - 1]
# Example
s = "aab"
print(minCut(s)) # Output: 1
C#
using System;
public class PalindromePartitioning {
public static int MinCut(string s) {
int n = s.Length;
bool[,] palindrome = new bool[n, n];
int[] dp = new int[n + 1];
for (int i = 0; i <= n; i++) dp[i] = i - 1;
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
palindrome[i, j] = (s[i] == s[j]) && (j - i <= 2 || palindrome[i + 1, j - 1]);
}
}
for (int i = 0; i < n; i++) {
if (palindrome[0, i]) dp[i] = 0;
else {
for (int j = 0; j < i; j++) {
if (palindrome[j + 1, i]) dp[i] = Math.Min(dp[i], dp[j] + 1);
}
}
}
return dp[n - 1];
}
public static void Main() {
string s = "aab";
Console.WriteLine(MinCut(s)); // Output: 1
}
}
JavaScript
function minCut(s) {
const n = s.length;
const palindrome = Array.from(Array(n), () => Array(n).fill(false));
const dp = Array.from({ length: n + 1 }, (_, i) => i - 1);
for (let i = n - 1; i >= 0; i--) {
for (let j = i; j < n; j++) {
palindrome[i][j] = (s[i] === s[j]) && (j - i <= 2 || palindrome[i + 1][j - 1]);
}
}
for (let i = 0; i < n; i++) {
if (palindrome[0][i]) dp[i] = 0;
else {
for (let j = 0; j < i; j++) {
if (palindrome[j + 1][i]) dp[i] = Math.min(dp[i], dp[j] + 1);
}
}
}
return dp[n - 1];
}
console.log(minCut("aab")); // Output: 1
Summary
- Time Complexity: O(n^2), where
nis the length of the string. - Space Complexity: O(n^2) due to the use of a 2D
palindrome[][]table. - Algorithm: Use dynamic programming to calculate the minimum cuts needed by iterating over the string, checking if substrings are palindromes and updating the DP table accordingly.