Do you think IIT Guwahati certified course can help you in your career?
Introduction
A palindrome is a sequence where elements of the sequence stay in the same position even after reversing the sequence. A palindromic string is a palindrome of alphabets. Examples of palindromic strings are MOM, RADAR, ROTOR, etc.
A substring of a non-palindromic string can also be a palindrome. e.g “banana”is a non-palindromic string while its substring “anana” is a palindrome. So, if we create a partition before index 1, we’ll get two substrings: “b” and “anana”. Both these substrings are palindromes. Such partitions are known as palindromic partitions. In the next section, we’ll discuss about a problem related to these palindromic partitions.
Given a string, find the minimum number of palindromic partitions required to make all the substrings of the string a palindrome.
Constraints
1 ≤ Length of the string ≤ 2000
Input
Enter Number of Test Cases: 3
Enter string: wow
Enter string: pranav
Enter string: banana
Output
Minimum number of cuts required for “wow:” 0
Minimum number of cuts required for “pranav”: 3
Minimum number of cuts required for “banana”: 1
Explanation
Method 1: Recursion
Consider the figure given below for the string “baaboo”.
If we look closely, substring “baab” is a palindrome. Now, we can try to find the number of palindromes in the rest of the substring.
Thus, to recursively solve the problem, we traverse from the beginning of the string. At every index ‘i’, we check if the substring from 0 to ‘i’th index is a palindrome. Once a palindrome is found, a cut is assumed. The number of palindromic partitions is recursively found on the remaining part of the substring.
Refer to the algorithm given below for a better understanding.
Algorithm
Set LENGTH = length of the given input.
Set START = 0 and END = LENGTH - 1. (‘START’ and ‘END’ represent the start and end indices of the currently assumed substring).
If ‘START’ is equal to ‘END’ or substring from ‘START’ to ‘END’ index is a palindrome, then:
Return 0. (It indicates that we have found a palindrome and no cut is required for this substring).
Set ANSWER = END - START (maximum palindromic partitions possible are between end and start).
For variable ‘i’ from ‘START’ to ‘END’:
If substring ‘START’ to ‘i’ is a palindrome (we can make a cut after this substring), then:
Set CURRENT_CUTS = 1 + recursive call with arguments i + 1 and ‘END’ (1 is added to count the current cut made).
If CURRENT_CUTS < ANSWER, (we found a better solution with less number of palindromic partitions ), then:
Set ANSWER = CURRENT_CUTS.
Return ‘ANSWER’.
Program
#include <iostream>
using namespace std;
string currentString;
// Function to check if the given string is a palindrome.
bool isPalindrome(int start, int end)
{
// Two pointers to check the 'START' and 'END' of the string.
while (start < end)
{
// If 'START' and 'END' don't match, not a palindrome.
if (currentString[start] != currentString[end])
return false;
start++;
end--;
}
// All characters matched. So, string is a palindrome.
return true;
}
int numCuts(int start, int end)
{
// No palindromic partitions required, if the string is already a palindrome.
if (start == end || isPalindrome(start, end))
return 0;
// Maximum cuts possible are between 'END' and 'START'.
int answer = end - start;
for (int i = start; i < end; i++)
{
// We can make a cut if the current substring is palindromeic.
if (isPalindrome(start, i))
{
// 1 is added to count the current cut made.
int currentCuts = 1 + numCuts(i + 1, end);
// If the number of cuts for this case are less than the previous case.
if (currentCuts < answer)
answer = currentCuts;
}
}
return answer;
}
int main()
{
int testCases;
cout << "Enter Number of Test Cases: ";
cin >> testCases;
while (testCases--)
{
cout << "Enter string: ";
cin >> currentString;
cout << "Minimum number of cuts required for \"";
// Calling the numCuts() function.
cout << currentString << "\" : " << numCuts(0, currentString.length() - 1) << endl;
}
}
You can also try this code with Online C++ Compiler
Time Complexity: In the worst case, no palindromic substring is possible in the string. So, every individual character is taken as a palindromic substring. The rest of the characters will form combinations with different lengths. So, the time complexity for recursive calls will be 2N, where ‘N’ represents the number of characters present in the string. Also, every substring is checked for the palindrome, which is a linear-time operation. So, the time complexity of this method is (N x 2N), where ‘N’ is the length of the string.
Space Complexity: Every recursive call requires O(1) space to store the ‘START’ and ‘END’ variables. The space complexity for the method becomes O(N), where ‘N’ is the depth of the recursion tree.
With the increase in the size of the recursive tree, the recursive function is called multiple times with the same input argument. Memoization can prune the recursive tree for finding palindromic partitions by storing the results of recursive calls. All you need to do is to make some tiny changes in our recursion recipe.
What should we memoize? Usually, the arguments that change in a recursive function are memoized. Let’s look at the arguments of the numCuts()’function in our Method 1: Recursion section. The arguments that change with every recursive call are: ‘START’ and ‘END’. Create a 2-D array (say ‘MEMO’) to store values of results formed by combinations of these arguments.
Revisit the Constraints section of the Problem Statement. The maximum length possible for the given string is 2000. So, the maximum number of indices possible is 2000. The size of the ‘MEMO’ array should be 2000 x 2000 at least to store all the possible indices.
To reduce the time complexity of the recursive function, we need to apply the following modifications:
Before making recursive calls check if the memo array has stored the result of the given state. If the memo array has already stored the result, return the stored value. Using the memo value will avoid redundant recursive calls.
Before returning to the previous recursive call, store the output of the current state to the memo array. So, when the same state is called recursively, the memo will provide the stored result.
Refer to the algorithm given below for a better understanding.
Algorithm
Set LENGTH = length of the given input.
Initialize a 2-D ‘MEMO’ array with -1 to store the outputs of the recursive calls.
Set START = 0 and END = LENGTH - 1. (‘START’ and ‘END’ represent the start and end indices of the currently assumed substring).
If MEMO[START ][END ] is not equal to -1, then:
Return MEMO[START ][END ].
If ‘START’ is equal to ‘END’ or substring from ‘START’ to ‘END’ index is a palindrome, then:
Return 0. (It indicates that we have found a palindrome and no cut is required for this substring).
Set ANSWER =.END - START (maximum palindromic partitions possible are between end and start).
For variable ‘i’ from ‘START’ to ‘END’:
If substring ‘START’ to ‘i’ is a palindrome (we can make a cut after this substring), then:
Set CURRENT_CUTS = 1 + recursive call with arguments i + 1 and end. (1 is added to count the current cut made.)
If CURRENT_CUTS < ANSWER, (we found a better solution with less number of palindromic partitions ), then:
Set ANSWER = CURRENT_CUTS.
Before returning, Set MEMO[START][END] = ANSWER.
Return ‘ANSWER’.
Program
#include <iostream>
#include <cstring>
using namespace std;
string currentString;
int memo[2001][2001];
// Function to check if the given string is a palindrome.
bool isPalindrome(int start, int end)
{
// Two pointers to check the start and end of string.
while (start < end)
{
// If start and end don't match, not a palindrome.
if (currentString[start] != currentString[end])
return false;
start++;
end--;
}
// All characters matched. So, string is a palindrome.
return true;
}
int numCuts(int start, int end)
{
// Check if the memo array has stored the result of the given state.
if (memo[start][end] != - 1)
return memo[start][end];
// No cuts required if string is already a palindrome.
if (start == end || isPalindrome(start, end))
return 0;
// Maximum cuts possible are between end and start.
int answer = end - start;
for (int i = start; i < end; i++)
{
// We can make a cut if current substring is palindromic.
if (isPalindrome(start, i))
{
// 1 is added to count current cut made.
int currentCuts = 1 + numCuts(i + 1, end);
// If number of cuts for this case are less than previous case.
if (currentCuts < answer)
answer = currentCuts;
}
}
// Store the output of the current state to the memo array.
memo[start][end] = answer;
return answer;
}
int main()
{
int testCases;
cout << "Enter Number of Test Cases: ";
cin >> testCases;
while (testCases--)
{
memset(memo, - 1, sizeof(memo));
cout << "Enter string: ";
cin >> currentString;
cout << "Minimum number of cuts required for \"";
// Calling the numCuts function.
cout << currentString << "\" : " << numCuts(0, currentString.length() - 1) << endl;
}
}
You can also try this code with Online C++ Compiler
Time Complexity: Memoization removes the redundant recursive calls. So, every unique combination of ‘START’ and ‘END’ runs only once. In the worst case, all the possible combinations of ‘START’ and ‘END’ are fed as function arguments. As ‘START’ and ‘END’ are indices, the time required for recursive calls is O(N2), where ‘N’ is the length of the string. Also, for each combination, the string is checked for a palindrome which requires linear time. So, the time complexity of the algorithm is O(N3), where ‘N’ is the length of the string.
Space Complexity: Extra space is required to memoize the code. The size of the ‘MEMO’ array is N x N, where ‘N’ is the length of the string. So, the space complexity is O(N2), where ‘N’ is the length of the string.
DP with memoization is a smart method to remove the redundancy in the recursive tree. Are recursive calls the only redundant part of our code? Look closely. For each ‘START’ to ‘i’ index in the recursive function, we perform a linear search to find if the current substring is a palindrome. Refer to the figure given below for illustration.
The substring “acoca” is already a palindrome. If we remove or add an equal number of the same characters at the beginning and end of a palindrome, the resultant string will still be a palindrome. In the example given above, we add one character(‘t’) at both sides of substring “acoca”. Without checking, we can say that the resultant substring “tacocat” is already a substring.
Let’s say the starting index of the substring “tacocat” is i, and the ending index is j. Refer to the figure given below for a better understanding.
Two following conditions should be fulfilled to check if the substring from index i to j is a palindrome.
Characters at index i and j should be equal to ensure that same characters are added to both sides of the smaller palindrome.
If the substring from index i + 1 to j - 1 is a palindrome. If the same characters are added at both the sides of a palindrome, the resulting substring from index i to j will also be a palindrome.
Precompute the palindromicity of all the possible substrings before calling the numCuts() function. Create a 2-D boolean array ‘IS_PAL’. The array size should be ‘N’ x ‘N’, where ‘N’ is the number of characters in the string. The rows numbers represent the ‘START’ index of the substring, while columns represent the ‘END’ index of the substring.
As every single character is a palindrome, we can set IS_PAL[i][j] = true where i == j.
For every two-characters string, if both the characters are the same, the string is a palindrome.
Now, for every character, check if the letters at index i and j are equal. If so, then check if the IS_PAL[i + 1][j - 1] is a palindrome. The resultant matrix may look like the figure given below.
Algorithm to Initialize IS_PAL
Set LENGTH = size of the ‘CURRENT_STRING’.
For i from 0 to LENGTH - 1, do:
Set IS_PAL[i][i] to true.
For i from 0 to LENGTH - 2, do:
If CURRENT_STRING[i] equal to CURRENT_STRING[i + 1], then:
Set IS_PAL[i][i + 1] to true.
Else:
Set IS_PAL[i][i + 1] to false.
For ‘CURRENT_LENGTH’ from 2 to ‘LENGTH’, do:
For ‘START’ from 0 and ‘END’ from ‘CURRENT_LENGTH’ till END < LENGTH , do:
If CURRENT_LENGTH[START] = CURRENT_LENGTH[END] and IS_PAL[START + 1][END - 1] = true, then:
IS_PAL[START][END] = true.
Else:
IS_PAL[START][END] = false.
Program
#include <iostream>
#include <cstring>
using namespace std;
string currentString;
int memo[2001][2001];
int isPal[2001][2001];
// Function to check if the given string is a palindrome.
void isPalindrome()
{
int length = currentString.length();
// Substrings with length 1 are set as palindromic.
for (int i = 0; i < length; i++)
isPal[i][i] = 1;
// For every two-letter string, if both the characters are the same, the string is a palindrome.
for (int i = 0; i < length - 1; i++)
{
if (currentString[i] == currentString[i + 1])
isPal[i][i + 1] = true;
}
for (int currentLength = 2; currentLength < length; currentLength++)
{
for (int start = 0, end = currentLength; end < length; start++, end++)
{
// If the substring is a palindrome and extremes are equal.
if ((currentString[start] == currentString[end]) && (isPal[start + 1][end - 1] == true))
isPal[start][end] = true;
else
isPal[start][end] = false;
}
}
}
int numCuts(int start, int end)
{
// Check if the memo array has stored the result of the given state.
if (memo[start][end] != - 1)
return memo[start][end];
// No palindromic partitions required if the string is already a palindrome.
if (start == end || isPal[start][end])
return 0;
// Maximum palindromic partitions possible are between end and start.
int answer = end - start;
for (int i = start; i < end; i++)
{
// We can make a cut if the current substring is palindromeic.
if (isPal[start][i])
{
// 1 is added to count the current cut made.
int currentCuts = 1 + numCuts(i + 1, end);
// If the number of cuts for this case are less than the previous case.
if (currentCuts < answer)
answer = currentCuts;
}
}
// Store the output of the current state to the memo array.
memo[start][end] = answer;
return answer;
}
int main()
{
int testCases;
cout << "Enter Number of Test Cases: ";
cin >> testCases;
while (testCases--)
{
memset(memo, - 1, sizeof(memo));
cout << "Enter string: ";
cin >> currentString;
cout << "Minimum number of cuts required for \"";
isPalindrome();
// Calling the numCuts function.
cout << currentString << "\" : " << numCuts(0, currentString.length() - 1) << endl;
}
}
You can also try this code with Online C++ Compiler
Time Complexity: In the previous method, for each combination, the string is checked for a palindrome that requires linear time. But now we have the ‘IS_PAL’ matrix for lookup, which checks if a string is a palindrome in linear time. Although the initialization of ‘IS_PAL’ runs on two nested loops, it’s done independently from the numCuts() function. So, we have modified the algorithm from O(N3) to O(2 x N2) time complexity. The time complexity of the modified algorithm is O(N2), where ‘N’ represents the length of the string.
Space complexity: Extra space is required for memoizing the code and for initializing the ‘IS_PAL’ lookup. The sizes of the ‘MEMO’ and ‘IS_PAL’ matrices are N x N, where ‘N’ is the length of the string. So, the space complexity is O(N2), where ‘N’ is the length of the string.
Congratulations on successfully learning the solution of the palindromic partitioning problem. You can also attempt the Longest Palindromic Subsequence problem now. You would have realised by now that it’s not wise to always create a dp table and try to fill in the values. To become a good coder, you need other ingredients too. You need to have a common sense with a bit of mind that’s ready to make adjustments to a solution. Adjustments that can make it more efficient.
Try to memoize the code if some value is computed again and again. You can practice and learn about memoization and many more cool techniques using our free practice platform Coding Ninjas Studio. So, keep practicing. That’s what good coders do.
24+ registered 
