Print all Palindromic Partitions of a String

Problem Statement

In the “Print all Palindromic Partitions of a String” problem we have given a string “s”. Write a program to print all possible palindromic partitioning of s. A palindrome is a word, number, phrase, or another sequence of characters that reads the same backward as forward, such as madam or racecar.

Input Format

The first and only one line containing the given string “s”.

Output Format

Print N lines where every line containing the partition of the string “s”. Here N is the total number of different partitions possible of string “s”.

Constraints

• 1<=|s|<=16
• s[i] must be a lower English letters

Example

aab

a a b 
aa b

Approach

The idea is to generate all possible substrings of a given string and expand each possibility if is a potential candidate. The first thing that comes to our mind is Depth First Search. In-Depth First Search, we recursively expand potential candidates until the defined goal is achieved. After that, we backtrack to explore the next potential candidate.

Backtracking incrementally build the candidates for the solution and discard the candidates (backtrack) if it doesn’t satisfy the condition. Below are some steps for the backtracking algorithm:

• Choose: Choose the potential candidate. Here, our potential candidates are all substrings that could be generated from the given string.
• Constraint: Define a constraint that must be satisfied by the chosen candidate. In this case, the constraint is that the string must be a palindrome.
• Goal: We must define the goal that determines if have found the required solution and we must backtrack. Here, our goal is achieved if we have reached the end of the string.

Algorithm for Print all Palindromic Partitions of a String

Here, we recursively traverse over the string in depth-first search fashion. For each recursive call, the beginning index of the string is given as start.

1. Iteratively generate all possible substrings beginning at $\text{start}$ index. The $\text{end}$ index increments from $\text{start}$ till the end of the string.
2. For each of the substring generated, check if it is a palindrome.
3. If the substring is a palindrome, the substring is a potential candidate. Add substring to the $\text{currentList}$ and perform a depth-first search on the remaining substring. If the current substring ends at index $\text{end}$, end+1 becomes the $\text{start}$ index for the next recursive call.
4. Backtrack if the index is greater than or equal to the string length and adds the $\text{currentList}$ to the result.

Implementation

C++ program for Print all Palindromic Partitions of a String

#include <bits/stdc++.h>

using namespace std;

bool check(string &s, int l, int r) 
{
    while (l < r) 
    {
        if (s[l++] != s[r--]) return false;
    }
    return true;
}
    
void dfs(vector<vector<string>> &r, string &s, int start, vector<string> &c) 
{
    if(start >= s.length())
    {
        r.push_back(c);
    }
    for(int i = start;i < s.length(); i++) 
    {
        if(check(s, start, i)) 
        {
            c.push_back(s.substr(start, i - start + 1));
            dfs(r, s, i + 1, c);
            c.pop_back();
        }
    }
}

int main()
{
   string s;
   cin>>s;
   vector<vector<string>> result;
   vector<string> current;
   dfs(result, s, 0, current);
   for(int i=0;i<result.size();i++)
   {
       for(int j=0;j<result[i].size();j++)
       {
           cout<<result[i][j]<<" ";
       }
       cout<<endl;
   }
   return 0;
}

Java program for Print all Palindromic Partitions of a String

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class sum
{ 
        static boolean isPalindrome(String s, int low, int high) 
        {
            while (low < high) {
                if (s.charAt(low++) != s.charAt(high--)) return false;
            }
            return true;
        }
        static void dfs(int start, List<List<String>> r, List<String> c, String s) 
        {
            if (start >= s.length()) 
            {
                r.add(new ArrayList<String>(c));
            }
            for (int end = start; end < s.length(); end++) {
                if(isPalindrome(s, start, end)) 
                {
                    c.add(s.substring(start, end + 1));
                    dfs(end + 1, r, c, s);
                    c.remove(c.size() - 1);
                }
            }
        }
        
  public static void main(String[] args) 
  { 
    Scanner sr = new Scanner(System.in); 
                String s = sr.next();
                List<List<String>> r = new ArrayList<List<String>>();
                List<String> c = new ArrayList<String>();
                dfs(0, r, c, s);
                for(int i=0;i<r.size();i++)
                {
                    for(int j=0;j<r.get(i).size();j++)
                    {
                        System.out.print(r.get(i).get(j).toString());
                        System.out.print(" ");
                    }
                    System.out.println();
                }
  } 
} 

racecar

r a c e c a r 
r a cec a r 
r aceca r 
racecar

Complexity Analysis for Print all Palindromic Partitions of a String

Time Complexity

O(N^(2*N)) where N is the length of the string “s”. This is the worst-case time complexity when all the possible substrings are palindrome.

Space Complexity

O(N) where N is the length of the string “s”. For s = aaa, the maximum depth of the recursive call stack is 3 which is equivalent to N.