Home » Technical Interview Questions » String Interview Questions » print all palindromic partitions

print all palindromic partitions

Reading Time - 2 mins

Given a string, write a function that will print all palindromic partitions of a given string


s = “bcdcb”

[‘b’, ‘c’, ‘d’, ‘c’, ‘b’]
[‘b’, “cdc”, ‘b’]

In this method the main idea is to use vectors, create a 2 dimensional vector to store all the partitions and a 1 dimensional vector to store the current partition


1. Traverse through every substring starting from first charcater

2. If the substring is a palindrome, then add it to the solution

3. recur for the remaining part

C++ Program

using namespace std;
//function to check if s is palindroem
bool isPalindrome(string s, int start, int end)
    while (start < end)
        if (s[start++] != s[end--])
            return false;
    return true;
//Recursive function,
//sol is a vector of vectors, each vector store a partition
//cPartition is a vector of strings to store current partition
void recAllPPartitions(vector<vector<string> >&sol, vector<string> &cPartition, 
                   int start, int n, string s)
    // If 'start' has reached len
    if (start >= n)
    // Pick all possible ending points for substrings
    for (int i=start; i<n; i++)
        // If substring s[start..i] is palindrome
        if (isPalindrome(s, start, i))
            // Add the substring to result
            cPartition.push_back(s.substr(start, i-start+1));
            // Recur for remaining remaining substring
            recAllPPartitions(sol, cPartition, i+1, n, s);
            // Remove substring s[start..i] from current 
            // partition
// Function to print all possible palindromic partitions of
// s. It mainly creates vectors and calls allPalPartUtil()
void printAllPPartitions(string s)
    int n = s.length();
    // To Store all palindromic partitions
    vector<vector<string> > sol;
    // To store current palindromic partition
    vector<string> cPartition; 
    // to generate all partitions
    recAllPPartitions(sol, cPartition, 0, n, s);
    // Print all partitions
    for (int i=0; i< sol.size(); i++ )
        cout<<"[ ";
        for (int j=0; j<sol[i].size(); j++)
            cout << sol[i][j] << " ";
        cout <<endl;

// Driver program
int main()
    string s = "bcdcb";
    return 0;

Try It

READ  Longest Common Prefix using Sorting



Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions