How to Find all the Palindromic Partitions of a String

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;
}

You can also try this code with Online C++ Compiler

Run Code

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.