1

Palindrome Partitioning

Difficulty: MEDIUM
Avg. time to solve
25 min
Success Rate
75%

Problem Statement
Suggest Edit

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 only line of input contains a string S.
Output Format :
Print all the possible palindromic partitions of the given string in a separate line.

Each substring of a partition is written within quotes(““) and separated by comma(,) and space, and each partition of the given string is written inside square brackets[].
Note:
All the substrings of a partition are sorted in lexicographical order in the output. You just need to return the partitions in any order.

You do not need to print or sort anything, it has already been taken care of. Just implement the function.
Constraints :
0 <= |S|<= 15
where |S| denotes the length of string S.

Time Limit: 1 sec
Sample Input 1:
aaC
Sample Output 1:
["C", "a", "a"]
["C", "aa"]
Explanation for input 1:
For the given string "aaC" there are two partitions in which all substring of partition is a palindrome.
Sample Input 2:
BaaB
Sample Output 2:
["B", "B", "a", "a"]
["B", "B", "aa"]
["BaaB"]
Explanation for input 2:
For the given string "BaaB", there are 3 partitions that can be made in which every substring is palindromic substrings.
Reset Code
Full screen
copy-code
Console