Welcome back, dear reader. So, how is it going with the backtracking and recursion? Hope that you are enjoying these problems .So, this problem is called PALINDROMIC PARTITIONS . What does this problem say? This problem says that we have to partition an input string in such a way that all its partitions are palindromes. For instance:
In the image above, we have shown some of the palindromic partitions of the string. Also, the complete string (if it is a palindrome) is also a palindromic partition. You may refer to the PALINDROME PARTITIONING OF A STRING to understand the question if you have any doubts about it. We recommend you try to solve the question on your own first and then move to the solution. Don't worry if you are stuck anywhere. What are we here for!!
Approach :
Time Complexity: O(2n)
Space Complexity: O(h) where h is the height of the recursion stack
Algorithm:
Take out a palindrome prefix from the question string. If there is no palindrome prefix, this string cannot be partitioned.
If you obtain a palindrome prefix, apply the recursion call by taking the remaining string as the question string and the prefix obtained as the answer so far.
Do this till the question string becomes empty. When the question string is empty, the answer so far (asf) will have the partitioned string. Print the answer and return from the recursion.
Explanation:
We will use the levels and options method to solve this problem. Let us consider the input string as "ababa". This is the string for which we will apply our procedure and find all the palindromic partitions.
What we will do at every level is that we will expand the string i.e. take out a palindromic prefix from the string till the question string becomes empty. You will understand this better when we will elaborate this procedure using a recursion tree. So, let's draw the recursion tree and then explain the procedure level by-level.
So, what is this tree all about? Let's try to understand it level by level.
First of all we have the input string "ababa". We are aiming at removing the prefixes from the question string and the removed prefix should be a palindrome.
From "ababa", we have 3 choices. Either we remove only 'a' which is a palindrome or we remove "aba" or we remove the entire string "ababa" as it is also a palindrome.
If we remove "a" from the string "ababa" then we will be left with only "baba" in the question string and our partition will be (a) for now. Similarly, if we remove the string "aba" then we will be left with "ba" as the question string and if we remove the entire string then we will not be left with any question string and the answer string will be a valid partition.
The numerator has the question string and the denominator is the answer so far (asf) for the partition. As you can see in the image above, we are removing the palindromic prefixes till the question string becomes empty.
The question string at the rightmost node (in the tree as per above diagram) is empty. So, a valid partition has been generated and we will not be able to generate any more partitions from here.
The question string in the middle node of the tree is "ba". So, we have only one option i.e. to remove "b". Why? We can only remove "b" because removing "ba" will not be valid as "ba" is not a palindrome. So, after removing "b" from it, we will have only "a" left in the question string and (aba)(b) in the answer. (see img--4)
After this, we have only "a" left in the question string (for the middle node in the tree at highest level). So, since "a" is a palindrome, it will be removed and we will get the question string as empty and the answer will have another valid partition (aba)(b)(a). This is shown in img-5
So, we hope that you have understood this procedure. We recommend you trace this entire tree and perform the procedure completely for the left-most branch of the tree. The complete tree is already shown in img-2. We also recommend that you watch the solution video to understand the above procedure completely and with more clarity. So, now the question is: how will we implement this procedure in the code?
How to implement this procedure?
To implement this procedure, we have to first make a Boolean function which will tell us whether a string is a palindrome or not. Why?
We have to remove the prefix from the question string and the prefix that we remove should be a palindrome. So, we will take a substring of the question string and check whether it is a palindrome or not. If it is, it will be removed and it will become our answer so far(asf). Then, we will apply the recursive call for the remaining string.
Base Case: As you have seen in the tree diagram also, the base case is when we reach a situation when the question string becomes empty and the answer string is actually the complete answer. Also, don't just return from the recursion call when we hit the base case. The base case is actually when we obtain the complete answer. So, first print the answer and then return from the recursion.
Now that we have understood the complete procedure, we will write the code for the same.
So, dear reader, we hope that you have understood the complete problem. The above code is explained in the solution video (6:14 onwards). So, you may refer to the solution video to understand the code if you have any doubts about it. Now, let us discuss the time and space complexity of the above code.
Analysis
Time Complexity:
By the process, you have an idea that the time complexity will depend upon the input string that how many prefixes can we break it into i.e. how many palindromic prefixes we get. For instance if we do not get any palindromic prefix, the time complexity is O(1) as there are no possible partitions for this. So, let us take an example which depicts the worst case scenario:
If all the characters in a string are the same then the number of recursive calls is equal to the length of the string. (shown in the diagram above with blue color). So, this is the worst case. Now ate every call, we have two choices, to be partitioned or not to be. So, the time complexity becomes 2n. Hence time complexity is O(2n).
Space Complexity:
The space complexity will also be of the same order approximately as when the time complexity is exponential, the space complexity also becomes near to exponential due to the maximum height of the stack. We can write that the spec complexity is O(h) where h is the height of the stack and the worst case of h will also be O(2n).
So, dear reader, we hope that you have understood the above time and space complexity analysis as well as the complete procedure and code. If you still have any doubts, refer to the complete solution video to clear all your doubts. With this we have completed this problem.
Suggestions:
Here are some suggestions from our side that you do not want to miss:
We suggest that you try to analyze the time and space complexity yourself and try to understand the best and worst case scenarios.
We also suggest that you make the complete tree and analyze the code and dry run the code with the tree once. This will help in your in depth understanding.
