Last Updated: 4 Apr, 2021
Find all distinct palindromic substrings of a given string
Moderate
Asked in companies
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
Approaches
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.
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.
- Check if S[ Start ] equal to S[ End ]
- 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.