Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Solution Using Recursion
2.1.
Algorithm 
2.2.
Implementation in C++
3.
Frequently Asked Questions
3.1.
What is a palindromic string?
3.2.
What is a standard palindrome?
3.3.
Can a number be a palindromic number?
3.4.
How can we copy a string into another string?
3.5.
How is a character array different from a string in CPP?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

How to Find all the Palindromic Partitions of a String

Author Ekansh Saxena
2 upvotes
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up
Bactracking and Recursion

Introduction

In this blog, we will be discussing the solution to the programming problem of finding all palindromic partitions of a string. Before diving further into the problem, let's begin with a brief introduction to palindromes.

Palindromes are any numbers or strings that are identical when read from left or right. For example 1331, 1234321 are palindromic numbers, and "abba" "mnpnm" are palindromic strings.

Now, coming back to the problem, we have a string, and we have to find all possible palindromic partitions. For example- If we had "success" as the input string, all possible partitions would be-

{s} {u} {c} {c} {e} {s} {s} 
{s} {u} {c} {c} {e} {ss}
{s} {u} {cc} {e} {s} {s}
{s} {u} {cc} {e} {ss}

A palindrome is a string that reads the same backward as forward.

There could be several methods to do this, but we will discuss a simple recursion-based method. So, let's dive right into the solution-

Also See, Data Structure

Solution Using Recursion

The problem of finding the palindromic partitions of a string can be solved using recursion. For this, we start with a two-dimensional vector for storing all possible palindromic partitions. Then we iterate through the string, and for each index, check if the string formed by it on its left is palindromic or not.

If the string on the left is palindromic, we push it into a temporary vector and recursively repeat the process for the substring on the right side of the index until we reach the end of the string. 

Once we reach the end of the string, we push the temporary vector into the 2-dimensional vector. Then we repeat the process of the next index. Once we have reached the last index of the string. We print the vectors of the strings stored in the 2dimensinal array, as it contains all the possible palindromic partitions of the string.

Algorithm 

  • Take string as input from the user.
  • Declare a 2 Dimensional vector to store all the palindromic partitions of the string.
  • Call the "startpartition" function that creates a temporary vector and calls the find partition function, taking the 2-dimensional vector, string, temporary vector, and index as arguments. 
  • The "findpartition" function first checks if the string up to the current index is palindrome or not with the "checkforpalindrome" function. If yes, then pushes it into the temporary vector and make the recursive call for the "findpartition" function using the remaining part of the string on the right of the index.

Once it reaches the end of the string, it pushes the temporary vector into the 2 Dimensional vectors. And make a recursive call to "findpartition" function with the next index of the string until we reach the end of the string.

  • Then we print the 2-dimensional vector containing all the possible palindromic partitions of the string

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
//To check if a string is palindrome or not.

bool checkforpal(string s)
{
    int length=s.length();
    length--;
    for(int i=0;i<length;i++)
    {
        if(s[i]!=s[length])
        {
            return false;
        }

        length--;
    }

    return true;
}

//To print the finally obtained palindromic partitions.
void printpartitions(vector<vector<string> > storepartitions)
{
    for(int i=0;i<storepartitions.size();i++)
    {
        for(int j=0;j<storepartitions[i].size();j++)
        {
            cout<<storepartitions[i][j]<<" ";
        }
        cout<<endl;
    }

    return;
}

/*Iterate through the whole string and for each index, check
  if the partitioned strings are palindromic. If yes, push
  them into the vector to store final result. */

void findpartitions(vector<vector<string> > &storepartitions, string &s, vector<string> &var, int pivot)
{
    int length=s.length();
    string str;
    vector<string> currstring = var;
    if (pivot == 0)
    {
        var.clear();
    }

    for (int i = pivot; i < length; i++)
    {
        str = str + s[i];
        
        //Calling for palindrome check.
        if (checkforpal(str))
        {
            var.push_back(str);
            if (i+1 < length)
            {
                findpartitions(storepartitions,s,var,i+1);
            }
            else
            {
                //Pushing into the vector.
                storepartitions.push_back(var);
            }
            
            var = currstring;
        }
    }

    return;
}

//To create partitions in the string and store the palindromic partitions in the resultant array.
void startpartition(string s, vector<vector<string> >&storepartitions)
{

    vector<string> var;
    findpartitions(storepartitions, s, var, 0);
    printpartitions(storepartitions);

    return;
}

//Driver function.
int main()
{

    string st;
    cin>>st;
    vector<vector<string> > storepartitions;
    startpartition(st, storepartitions);

    return 0;
}

Input

success 

Output

s u c c e s s 
s u c c e ss
s u cc e s s
s u cc e ss

The time complexity of the above approach is O(N*2^N)

The space complexity of the above approach is- O(N)

Check out this problem - Check If A String Is Palindrome

You can also read about Palindrome Number in Python here.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is a palindromic string?

A string is called a palindromic string if it is identical when read from left to right or right to left. For example- reviver, redivider are palindromic strings.

What is a standard palindrome?

Standard palindrome refers to a phrase that is identical,  from left to right or right or left, given that we remove the spaces and punctuation marks in between. For example, "I'm Adam" is an example of the standard palindrome.

Can a number be a palindromic number?

Yes, if a remains the same even after reversing its digits, it is a palindromic number.

How can we copy a string into another string?

We can use strcpy function to copy a string into another string. The syntax for using strcpy is - char* strcpy(char* destination_string, const char* source_string);

How is a character array different from a string in CPP?

Character arrays behave like any ordinary array. Whereas the string is a class in CPP, also the strings have well-defined methods and functions that allow us much more functionality than the character arrays.

Conclusion

In this blog, we learned about finding all the palindromic partitions of a string using a recursion-based approach-

We started with declaring a two-dimensional array to store the palindromic partitions of the string. We started iterating through the string, and for each index, check if the string is palindromic up to there or not. If it is palindromic, repeat the process for the remaining indices on the right of the current index and keep pushing the palindromic partitions in a temporary vector. Once we reach the end of the string and all the partitionings on the right of the current index are palindromic, push the temporary vector into the two-dimensional vector.

Recommended problems -

 

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Previous article
Different Ways to Add Parentheses
Next article
Add Two Numbers Represented by a Linked List
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass