Problem Statement
Given a string s, partition s such that every partition of s is a palindrome. Find the minimum number of cuts to form a palindromic partition of s.
Palindrome: A string is called a palindrome when it is read the same way both forwards and backward.
Sample Test Cases
Input 1: s = “Coffee”
Output 1: 3
Explanation 1:
From the picture above, it is evident that a minimum of 3 partitions is needed to make a palindromic partition of s.
Input 2: s = “ababbbabbababa”
Output 2: 3
Explanation 2:
From the picture above, it is evident that 3 cuts are needed for this string.
Naive Approach
We can solve this problem naively, using a recursive backtracking-based algorithm. Observe that if the string is a palindrome, we will need 0 cuts for it (this will be the base case for our recursion). Else, we can try to put cuts at all possible positions in the string and try to calculate the number of cuts needed to make a valid palindromic partitioning over all possible combinations of cuts and return the minimum among them.
C++ Implementation
int checkPalindrome(string & s, int start, int end) {
while (start < end) {
if (s[start] != s[end]) {
return 0;
}
start++;
end--;
}
return 1;
}
int minimumCuts(string & s, int i, int j) {
if (checkPalindrome(s, i, j) || i >= j) {
return 0;
}
int answer = INT_MAX;
int countCuts = -1;
for (int k = i; k < j; k++) {
countCuts = minimumCuts(s, i, k) + minimumCuts(s, k + 1, j);
countCuts += 1;
answer = min(answer, countCuts);
}
return answer;
}
int getMinCuts(string s) {
int n = s.length();
return minimumCuts(s, 0, n - 1);
}
Java Implementation
public static int checkPalindrome(String s, int start, int end) {
while (start < end) {
if (s.charAt(start) != s.charAt(end)) {
return 0;
}
start++;
end--;
}
return 1;
}
public static int minimumCuts(String s, int i, int j) {
if (checkPalindrome(s, i, j) == 1 || i >= j) {
return 0;
}
int answer = Integer.MAX_VALUE;
int countCuts = -1;
for (int k = i; k < j; k++) {
countCuts = minimumCuts(s, i, k) + minimumCuts(s, k + 1, j);
countCuts += 1;
answer = Math.min(answer, countCuts);
}
return answer;
}
public static int getMinCuts(String s) {
int n = s.length();
return minimumCuts(s, 0, n - 1);
}
Python Implementation
def checkPalindrome(s, start, end):
while start < end:
if s[start] != s[end]:
return 0
start += 1
end -= 1
return 1
def minimumCuts(s, i, j):
if checkPalindrome(s, i, j) or i >= j:
return 0
answer = 999999
countCuts = -1
for k in range(i, j):
countCuts = minimumCuts(s, i, k) + minimumCuts(s, k + 1, j)
countCuts += 1
answer = min(answer, countCuts)
return answer
def getMinCuts(s):
n = len(s)
Complexity Analysis
- Time Complexity: Exponential.
- Space Complexity: O(1) if recursion stack space is excluded.
Memoization Based Approach
Consider the case when we partition a string from say [0, i], [i + 1, j], [j + 1, n] and we know the cost for each of these substrings. Now, if we want to compute the cost for a combination of cuts such the substrings corresponds to [0, i], [i + 1, l], [l + 1, j], [j + 1, n], then in our brute force method we will again compute the costs for the substrings [0, i] and [j + 1, n].
So, we can observe that there will be multiple such redundant function calls. To prevent these redundant function calls, we can memoize/cache the results of these function calls in some containers, and recompute them in O(1) when needed. This will reduce our computational complexity from exponential to polynomial time at the trade-off of some extra space.
C++ Code
int checkPalindrome(string & s, int start, int end) {
while (start < end) {
if (s[start] != s[end]) {
return 0;
}
start++;
end--;
}
return 1;
}
int minimumCuts(string & s, int i, int j, vector < vector < int >> & dp) {
if (checkPalindrome(s, i, j) || i >= j) {
return dp[i][j] = 0;
}
if (dp[i][j] != -1) {
return dp[i][j];
}
int answer = INT_MAX;
int countCuts = -1;
for (int k = i; k < j; k++) {
countCuts = minimumCuts(s, i, k, dp) + minimumCuts(s, k + 1, j, dp);
countCuts += 1;
answer = min(answer, countCuts);
}
dp[i][j] = answer;
return dp[i][j];
}
int getMinCuts(string s) {
int n = s.length();
vector < vector < int >> dp(n + 1, vector < int > (n + 1, -1));
return minimumCuts(s, 0, n - 1, dp);
}
Java Code
public static int checkPalindrome(String s, int start, int end) {
while (start < end) {
if (s.charAt(start) != s.charAt(end)) {
return 0;
}
start++;
end--;
}
return 1;
}
public static int minimumCuts(String s, int i, int j, int[][] dp) {
if (checkPalindrome(s, i, j) == 1 || i >= j) {
dp[i][j] = 0;
return dp[i][j];
}
if (dp[i][j] != -1) {
return dp[i][j];
}
int answer = Integer.MAX_VALUE;
int countCuts = -1;
for (int k = i; k < j; k++) {
countCuts = minimumCuts(s, i, k, dp) + minimumCuts(s, k + 1, j, dp);
countCuts += 1;
answer = Math.min(answer, countCuts);
}
dp[i][j] = answer;
return dp[i][j];
}
public static int getMinCuts(String s) {
int n = s.length();
int[][] dp = new int[n + 1][n + 1];
for (int i = 0; i <= n; i++) {
Arrays.fill(dp[i], -1);
}
return minimumCuts(s, 0, n - 1, dp);
}
Python Code
def checkPalindrome(s, start, end):
while start < end:
if s[start] != s[end]:
return 0
start += 1
end -= 1
return 1
def minimumCuts(s, i, j, dp):
if checkPalindrome(s, i, j) or i >= j:
dp[i][j] = 0
return dp[i][j]
if dp[i][j] != -1:
return dp[i][j]
answer = 999999
countCuts = -1
for k in range(i, j):
countCuts = minimumCuts(s, i, k, dp) + minimumCuts(s, k + 1, j, dp)
countCuts += 1
answer = min(answer, countCuts)
dp[i][j] = answer
return dp[i][j]
def getMinCuts(s):
n = len(s)
dp = [[-1 for i in range(n + 1)] for j in range(n + 1)]
return minimumCuts(s, 0, n - 1, dp)
Complexity Analysis
- Time Complexity: O(n2)
- Space Complexity: O(n2)
Iterative DP Based Approach
We can solve this problem by using Dynamic Programming to compute the results of the overlapping problems shown in the previous example under memoization and storing them in a DP Table. To solve this problem effectively, we will need two DP arrays, as follows,
- DP[i][j] = True if the substring from [i, j] is a palindrome, else False.
- DpCut[i] = Minimum number of cuts required for prefix from 0 to i.
Using these 2 DP arrays, we can compute the answer for the entire string, and the result will be stored in DpCut[string.length – 1]. If we compute the DP array beforehand and then using its results compute the DpCut array, we can further reduce the time complexity of the problem to Quadratic Asymptotics.
Check the implementation for a better understanding of the approach:
C++ Code – DP Approach
int getMinCuts(string & s) {
int n = s.length();
vector < int > DpCut(n);
int dp[n][n];
memset(dp, false, sizeof(dp));
for (int i = 0; i < n; i++) {
int minimumCuts = i;
for (int j = 0; j <= i; j++) {
if (s[i] == s[j]) {
if (((i < (j + 2) || dp[j + 1][i - 1]))) {
dp[j][i] = true;
if (j == 0) {
minimumCuts = 0;
} else {
minimumCuts = min(minimumCuts, DpCut[j - 1] + 1);
}
}
}
}
DpCut[i] = minimumCuts;
}
return DpCut[n - 1];
}
Java Code – DP Approach
public static int getMinCuts(String s) {
int n = s.length();
int[] DpCut = new int[n];
boolean[][] dp = new boolean[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(dp[i], false);
}
for (int i = 0; i < n; i++) {
int minimumCuts = i;
for (int j = 0; j <= i; j++) {
if (s.charAt(i) == s.charAt(j)) {
if (i < (j + 2) || dp[j + 1][i - 1]) {
dp[j][i] = true;
if (j == 0) {
minimumCuts = 0;
} else {
minimumCuts = Math.min(minimumCuts, DpCut[j - 1] + 1);
}
}
}
}
DpCut[i] = minimumCuts;
}
return DpCut[n - 1];
}
Python Code – DP Approach
def getMinCuts(s):
n = len(s)
cutDp = [0] * n
dp = [[False for i in range(n)] for j in range(n)]
for i in range(n):
minimumCuts = i
for j in range(i + 1):
if s[i] == s[j]:
if i < (j + 2) or dp[j + 1][i - 1]:
dp[j][i] = True
if j == 0:
minimumCuts = 0
else:
minimumCuts = min(minimumCuts, cutDp[j - 1] + 1)
cutDp[i] = minimumCuts
return cutDp[n - 1]
Complexity Analysis
- Time Complexity: O(n2)
- Space Complexity: O(n2)
FAQs
Q. How to identify that a problem can be solved by Dynamic Programming?
A. A problem can be solved using Dynamic Programming if it contains some Optimal Substructure and Overlapping Subproblems.
Q. Which of the above approaches is expected to be the fastest?
A. The iterative DP approach is expected to be faster in practice than the Recursive Memoization approach because repeated function calls often bring with them some associated overhead which takes some extra time.
