Find all distinct palindromic substrings of a given string

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
2 upvotes
Asked in companies
MakeMyTripOlaSAP Labs

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
aba
aabb
Sample Output 1:
a aba b
a aa b bb
Explanation of sample input 1:
For the first test case, 
All the possible substrings are [ ‘a’, ‘b’, ‘ab’, ‘ba’, ‘aba’ ] out of which [ ‘a’, ‘aba', 'b’ ] are 
palindromic substrings.

For the second test case,
All the possible substrings are [ ‘a’, ‘b’, ‘aa’, ‘ab’, ‘bb’, ‘aab’, ‘abb’ , ‘aabb’ ] out of which [ 
‘a’, ‘b’, ‘aa’, ‘bb’ ] are palindromic substrings.
Sample Input 2:
2
babbb
abcdc
Sample Output 2:
a b bab bb bbb 
a b c cdc d
Hint

Check for each substring whether the substring is palindromic or not.

Approaches (2)
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.
Time Complexity

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).

Space Complexity

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).

Code Solution
(100% EXP penalty)
Find all distinct palindromic substrings of a given string
Full screen
Console