New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Palindrome Partitioning

Contributed by

Ashwani

Last Updated: 23 Feb, 2023

Medium

0/80

Avg time to solve 25 mins

Success Rate 75 %

34 upvotes

Problem Statement

You are given a string 'S'. Your task is to 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 only line of input contains a string 'S'.

Output Format :

For each test case, 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[].

The output of each test case will be printed in a separate line.

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.

Auto

Console