Palindrome Partitions

Easy
0/40
2 upvotes
Asked in companies
AmazonRedBusGoogle inc

Problem statement

You are given a string S, partition S such that every substring of the partition is a palindrome. You need to return all possible palindrome partitioning of S.

Note: A substring is a contiguous segment of a string.

For Example : 
For a given string “BaaB.”
3 possible palindrome partitioning of the given string are:
{“B”, “a”, “a”, “B”}
{“B”, “aa”, “B”}
{“BaaB”}
Every substring of all the above partitions of “BaaB” is a palindrome.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases. The test cases follow.
The first line of each test case contains a string S.
Output Format : 
Print each palindromic partition of the given string in a separate line. Print the substrings of a string separated by a single space.
Note: 
You do not need to print. It has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 5
0 <= |S|<= 12
Where ‘T’ denotes the number of test cases, and |S| denotes the length of string S.

Time Limit: 1 sec
Sample Input 1:
2
aaC
bb
Sample Output 1:
a a C
aa C
b b
bb
Explanation for input 1:
In the first test case, there are two partitions in which all substrings of the partition are palindromes. The partitions are {“a”, ”a”, ”C”} and {“aa”, “C”}.
In the second test case, there are two partitions in which all substrings of the partition are palindromes. The partitions are {“b”, ”b”} and {“bb”}.
Sample Input 2:
2
BaaB
abc
Sample Output 2:
B a a B
B aa B
BaaB
a b c
Explanation for input 2:
In the first test case, there are three partitions in which all substrings of the partition are palindromes. The partitions are {“B”, ”a”, “a”, ”B”}, {“B”, “aa”, “B”}, {“BaaB”}.
In the second test case, there is only one partition in which all substrings of the partition are palindromes. The partition is {“a”, “b”, “c”}.
Hint

Can you try to generate all the partitions using recursion?

Approaches (1)
Recursion based Approach
  1. The idea is to generate all possible substrings of a given string recursively using backtracking.
  2. Let’s define a recursive function generatePartitions(S,start,ans,currentList). Here, ‘S’ denotes the given string, “start” is our current index, “ans” is an array to store all the partitions, “currentList” is an array that contains the partitions of the string made before index “start”.
    1. For each recursive call, the starting index of the string is “start”. Now, iteratively generate all possible substrings beginning at the “start” index and ending at let’s say at the ‘K’th index. The value of ‘K’ begins from start and increments by 1 till ‘K’ reaches the end of the string.
    2. For every substring(from index “start” to ‘K’, both inclusive) generated check if it is a palindrome. If the substring is a palindrome, then add it to list “currentList” then recur for the remaining part of a string(with “start” = K+1).
  3. At last, we backtrack if the “start” index reaches the end of the string and add the “currentList” to the “ans” list.
  4. Now “ans” will contain all palindromic partitions of the string. Hence we will return “ans”.
Time Complexity

O((N^2)*(2^N)), where N is the length of the String.

 

In the worst case, when all substrings are palindromes. Then there will be 2^(N)  possible substring partitions, and for each substring, it takes O(N) time to generate the substring and to check if it is palindrome or not it will again take O(N) time. Thus, the overall complexity will be O((N^2)*(2^N)).

Space Complexity

O((N)*(2^N)), where N is the length of the string.

 

In the worst case, when all substrings are palindromes. Then there will be 2N  possible partitions, and for each partition, we will need O(N) space to store the substrings. Thus, the total space complexity is O((N)*(2^N)).

Code Solution
(100% EXP penalty)
Palindrome Partitions
Full screen
Console