Last Updated: 17 Dec, 2020

Palindrome Partitions

Easy

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

The idea is to generate all possible substrings of a given string recursively using backtracking.
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).
At last, we backtrack if the “start” index reaches the end of the string and add the “currentList” to the “ans” list.
Now “ans” will contain all palindromic partitions of the string. Hence we will return “ans”.

Solve now