Find all distinct palindromic substrings of a given string
Ninja did not do homework. As a penalty, the teacher has given a string ‘S’ to ninja and asked him to print all distinct palindromic substrings of the given string. A string is said to be palindrome if the reverse of the string is the same as the string itself. For example, the string “bccb” is a palindrome, but the string “def” is not a palindrome.

Input Format:

The first line of input contains an integer ‘T’, denoting the number of test cases. The first and only line of each test case contains the string ‘S’.

Output Format:

For each test case, print all distinct palindromic substrings of the given string. Print the substrings in sorted manner and they should be space-separated. Print the output of each test case in a separate line.

Constraints:

1

Question

Find all distinct palindromic substrings of a given string

Ninja did not do homework. As a penalty, the teacher has given a string ‘S’ to ninja and asked him to print all distinct palindromic substrings of the given string. A string is said to be palindrome if the reverse of the string is the same as the string itself. For example, the string “bccb” is a palindrome, but the string “def” is not a palindrome.

Input Format:

The first line of input contains an integer ‘T’, denoting the number of test cases.
The first and only line of each test case contains the string ‘S’.

Output Format:

For each test case, print all distinct palindromic substrings of the given string. Print the substrings in sorted manner and they should be space-separated.    

Print the output of each test case in a separate line.

Constraints:

1 <= T <= 10
1 <= |S| <= 1000

String S contains lowercase English letters only.

Where ‘T’ represents the number of test cases and ‘S’ represents the given string.

Time limit: 1 sec

Accepted Answer

Step 1 : Find all the palindromic sub-strings
Step 2 : Remove duplicate palindromes
Step 3 : Print the distinct palindromes and number of such palindromes

Accepted Answer

Brute force

The idea is to simply use three loops and check for each substring if it is palindromic and add it to our output array accordingly. In our implementation, we will be using a Hashmap to keep track of palindromic substrings and will sort all palindromic substrings before returning them.

Algorithm:

Maintain a Hashmap M.
Let N be the length of the String S.
Iterate I from 0 to N-1,
- Iterate J from I to N-1
- Check if S[ I:J ] is a palindrome. Here, S[ I:J ] denotes the substring of S from index I to J (Both inclusive).
  - Insert S[ I:J ] into the HashMap M, if it is already not present in it.
After finding all the substring, we will store the keys of M into an array of strings.
Sort the array of strings and then return the final array.

Space Complexity: O(n^2)Explanation:

O(N^2), where N is the length of the string S.

There can be at most O(N^2) distinct palindromic substrings in the given string. Hence, the overall Space Complexity is O(N^2).

Time Complexity: O(n^3)Explanation:

O(N^3), where N is the length of the string S.

There are O(N^2) substrings of the String S, and it takes O(N) time to traverse through one substring. Hence, the overall Time Complexity is O(N^3).

Java (SE 1.8)

/*
	Time Complexity: O(N ^ 3)
	Space Complexity: O(N ^ 2)

	Where 'N' is the length of the string S
*/

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

public class Solution 
{
    public static ArrayList distinctPalindrome(String s)
    {
		Map m = new HashMap<>();
		int n = s.length();

		for (int i = 0; i < n; i++) 
		{
			// For each character in the string, consider all odd and even lengths Substrings centered at the character. 
			// At a time , Compare the left and right character and if they are equal then expand the string
			
			String substring = "";
			
			for (int j = i; j < n; j++) 
			{
				substring = substring + s.charAt(j);

				int start = 0, end = j - i;

				// Check if Substring from index i to j (Both inclusive) is a palindrome
				int isPalindrome = 1;

				while (start < end) 
				{

					if (substring.charAt(start) != substring.charAt(end)) 
					{

						isPalindrome = 0;
						break;
					}
					start++;
					end--;
				}

				// If the Substring is a palindrome then insert Substring into M 
				if (isPalindrome == 1) 
				{
					m.put(substring, 1);
				}
			}
		}

		// Insert all Distinct Substrings of S into array of strings 
		ArrayList palindromeSubstrings = new ArrayList();

		for (Map.Entry pairEntry : m.entrySet()) 
		{
			palindromeSubstrings.add(pairEntry.getKey());
		}
		// Sort the array of strings and return the final array
		Collections.sort(palindromeSubstrings);
		
		return palindromeSubstrings;
		        
    }

}

Python (3.5)

'''

   Time Complexity: O(N^3)

   Space Complexity: O(N^2)



   Where 'N' is the length of the string S

'''



def distinctPalindrome(s):

    m = {}

    n = len(s)



    for i in range(n):



        substring = ''



        for j in range(i, n):



            substring = substring + s[j]



            start , end= 0, j - i



            # Check if Substring from index i to j (Both inclusive) is a palindrome

            isPalindrome = 1



            while (start < end) :

                

                if (substring[start] != substring[end]) :				

                    isPalindrome = 0

                    break;

                             

                start += 1

                end -= 1

            



            # If the Substring is a palindrome then insert Substring into M 

            if (isPalindrome) :

                m[substring] = 1



    # Insert all Distinct Substrings of S into array of strings 

    palindromeSubstrings = []



    for it in m.keys(): 

        palindromeSubstrings.append(it)



    # Sort the array of strings and return the final array

    palindromeSubstrings.sort()



    return palindromeSubstrings

C++ (g++ 5.4)

/*

   Time Complexity: O(N^3)

   Space Complexity: O(N^2)



   Where N is the length of the string S

*/



#include

#include



vector  distinctPalindrome(string &s) 

{

    unordered_map  m;

    int n = s.length();



    for (int i = 0; i	{

        string substring;



        for (int j = i; j < n; j++) 

		{

            substring = substring + s[j];



            int start = 0, end = j - i;



            // Check if Substring from index i to j (Both inclusive) is a palindrome

            int isPalindrome = 1;



            while (start < end) 

			{



                if (substring[start] != substring[end]) 

				{



                    isPalindrome = 0;

                    break;

                }

                start++;

                end--;

            }



            // If the Substring is a palindrome then insert Substring into M 

            if (isPalindrome) 

			{

                m[substring] = 1;

            }

        }

    }



    // Insert all distinct Substrings of S into array of strings 

    vector  palindromeSubstrings;



    for (unordered_map::iterator it = m.begin(); it != m.end(); it++) 

	{

        palindromeSubstrings.push_back(it -> first);

    }



    // Sort the array of strings and return the final array

    sort(palindromeSubstrings.begin(), palindromeSubstrings.end());



    return palindromeSubstrings;



}

Accepted Answer

Solution using modified Manacher’s algorithm

For each character in the string, consider all odd and even lengths substrings centered at the character. For odd length substrings, keep a string and append the character in the string, compare the left and right characters. If both of them are equal then we can expand that string to left and right as including that left and right character in the string will also result in a palindromic substring. For even length substrings, keep the string empty and expand.

Odd length :

At position I, Each character at J distance to its left and right should be the same to create a palindromic substring of odd length ( S[ I-J ] = S[ I+J ] ).

For example, Consider S = ’abcbd’ and odd length substrings centered at position 3 will be [ ‘c’ , ‘bcb’, ‘abcbd’ ] and palindromic substrings among them are [ ‘c’ , ‘bcb’ ] .

Even length :

Consider S =’dabbac’ and even length substrings at position 4 will be [ ‘bb’, ‘abba’, ‘dabbac’ ] and palindromic substrings are [ ‘bb’, ‘abba’ ].

Consider S =’abcbd’ and even length substrings centered at position 3 will be [ ‘bc’ , ‘abcb’ ], out of which no substring is palindrome.

We will use a Hashmap to keep track of all palindromic substrings and sort all palindromic substrings before printing.

Algorithm:

Maintain a Hashmap M.
Let N be the length of the String S.
Iterate I from 0 to N - 1,
- Firstly we will find the odd length palindromic substrings. To find them, we will set the variable Start as I - 1 and the variable End as I + 1.
- While both the variables Start, End lies between 0 to N - 1, then
  - Check if S[ Start ] equal to S[ End ]
    - Insert S[ Start:End ] into the HashMap, if it is already not present in it. Here, S[ Start:End ] is the substring of S from Start to End index.
  - Otherwise, terminate the loop
  - Decrement Start by 1 and increment End by 1.
To find the even length palindromic substrings, we will take the variable Start as I - 1 and the variable end as I and will perform the same procedure as mentioned above.
After iterating through the input string completely, we will store the keys of the HashMap into an array of strings
Sort the array of strings and return the final array.

Space Complexity: O(n^2)Explanation:

O(N^2), where N is the length of the string S.

There can be at most O(N^2) distinct palindromic substrings of the given string. Hence, the overall Space Complexity is O(N^2).

Time Complexity: O(n^2)Explanation:

O(N^2), where N is the length of the string S.

We are traversing through the string using two loops. Hence, the overall Time Complexity is O(N^2).

Java (SE 1.8)

/*
	Time Complexity: O(N ^ 2)
	Space Complexity: O(N ^ 2)

	Where 'N' is the length of the string S
*/
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

public class Solution 
{
    public static ArrayList distinctPalindrome(String s)
    {
		Map m = new HashMap<>();
		int n = s.length();

		for (int i = 0; i < n; i++) 
		{
			// For each character in the string, consider all odd and even lengths Substrings centered at the character. 
			// At a time , Compare the left and right character and if they are equal then expand the string
			
			String substring = "";
			substring += s.charAt(i);

			int start = i - 1, end = i + 1;

			// Considering Substring of length 1
			m.put(substring, 1);

			// Considering odd length Substrings 	
			while (start >= 0 && end < n && s.charAt(start) == s.charAt(end)) 
			{
				substring = s.charAt(start) + substring + s.charAt(end);

				// Insert the Substring into HashMap
				m.put(substring, 1);

				start--;
				end++;
			}

			substring = "";
			start = i - 1;
			end = i;

			// Considering even length Substrings
			while (start >= 0 && end < n && s.charAt(start) == s.charAt(end)) 
			{
				substring = s.charAt(start) + substring + s.charAt(end);

				// Insert the Substring into HashMap
				m.put(substring, 1);
				
				start--;
				end++;
			}
		}

		// Insert all Distinct Substrings of S into array of strings 
		ArrayList palindromeSubstrings = new ArrayList();

		for (Map.Entry pairEntry : m.entrySet()) 
		{
			palindromeSubstrings.add(pairEntry.getKey());
		}
		// Sort the array of strings and return the final array
		Collections.sort(palindromeSubstrings);
		
		return palindromeSubstrings;
		        
    }

}

C++ (g++ 5.4)

/*

   Time Complexity: O(N^2)

   Space Complexity: O(N^2)



   Where 'N' is the length of the string S

*/



#include

#include



vector distinctPalindrome(string &s)

{

    unordered_map m;

    int n = s.length();



    for (int i = 0; i < n; i++) 

    {

        // For each character in the string, consider all odd and even lengths Substrings centered at the character. 

        // At a time , Compare the left and right character and if they are equal then expand the string

        

        string substring;

        substring += s[i];



        int start = i - 1, end = i + 1;



        // Considering Substring of length 1

        m[substring] = 1;



        // Considering odd length Substrings 	

        while (start >= 0 && end < n && s[start] == s[end]) 

        {

            substring = s[start] + substring + s[end];



            // Insert the Substring into HashMap

            m[substring] = true;



            start--;

            end++;

        }



        substring.clear();

        start = i - 1;

        end = i;



        // Considering even length Substrings

        while (start >= 0 && end < n && s[start] == s[end]) 

        {

            substring = s[start] + substring + s[end];



            // Insert the Substring into HashMap

            m[substring] = 1;

            

            start--;

            end++;

        }

    }



    // Insert all Distinct Substrings of S into array of strings 

    vector palindromeSubstrings;



    for (unordered_map::iterator it = m.begin(); it != m.end(); it++) 

    {

        palindromeSubstrings.push_back(it -> first);

    }



    // Sort the array of strings and return the final array

    sort(palindromeSubstrings.begin(), palindromeSubstrings.end());



    return palindromeSubstrings;



}

Python (3.5)

'''

   Time Complexity: O(N^2)

   Space Complexity: O(N^2)



   Where 'N' is the length of the string S

'''



def distinctPalindrome(s):

    m = {}

    n = len(s)



    for i in range(n):



        # For each character in the string, consider all odd and even lengths Substrings centered at the character. 

        # At a time , Compare the left and right character and if they are equal then expand the string

 	

        substring = s[i]

        start, end = i - 1, i + 1



        # Considering Substring of length 1 

        m[substring] = 1



        # Considering odd length Substrings

        while (start >= 0 and end < n and s[start] == s[end]): 

		

            substring = s[start] + substring + s[end]



            # Insert the Substring into HashMap

            m[substring] = 1



            start-=1

            end+=1



        substring  = ""

        start = i - 1

        end = i



        # Considering even length Substring

        while (start >= 0 and end < n and s[start] == s[end]):



            substring = s[start] + substring + s[end]

            

            # Insert the Substring into HashMap

            m[substring] = 1



            start-=1

            end+=1



    # Insert all Distinct Substrings of S into array of strings 

    palindromeSubstrings = []



    for it in m.keys(): 

        palindromeSubstrings.append(it)



    # Sort the array of strings and return the final array

    palindromeSubstrings.sort()



    return palindromeSubstrings

Input Format:

Output Format:

Constraints:

Top Ola Cabs SDE-2 interview questions & answers

Popular interview questions of SDE-2