Find all distinct palindromic sub-strings of a given string

Given a string of lowercase ASCII characters, find all distinct continuous palindromic sub-strings of it. 

Examples: 

Input: str = "abaaa"
Output:  Below are 5 palindrome sub-strings
a
aa
aaa
aba
b
Input: str = "geek"
Output:  Below are 4 palindrome sub-strings
e
ee
g
k

BRUTE APPROACH

Intuition:

1. We declare a boolean 2-D array and fill it diagonally.
2. We check for every gap.ie(0,1,2,…..)
3. suppose gap=0., that means there is only one element and we put  true since  a single character is palindrome
4. if gap = 1, we check whether extremes are same and if so we put true,else false;
5. else for any other value of gap, we check if extremes are same and dp[i+1][j-1] yields true  and if so then we put true else false;
6. at every time when a true is encountered we add the string in the set data structure.
7. Atlast we return the ans

Implementation:

No of distinct palindromic substrings are : 5
a
aa
aaa
aba
b

Time Complexity: O(N^2 * log(N)) since we are iterating through the matrix and while doing so we put elements in set which takes log(N) time
Space Complexity: O(N^2) since we using 2-D array

Method 1:

Step 1: Finding all palindromes using modified Manacher’s algorithm: 
Considering each character as a pivot, expand on both sides to find the length of both even and odd length palindromes centered at the pivot character under consideration and store the length in the 2 arrays (odd & even). 
Time complexity for this step is O(n^2)

Step 2: Inserting all the found palindromes in a HashMap: 
Insert all the palindromes found from the previous step into a HashMap. Also insert all the individual characters from the string into the HashMap (to generate distinct single letter palindromic sub-strings). 
Time complexity of this step is O(n^3) assuming that the hash insert search takes O(1) time. Note that there can be at most O(n^2) palindrome sub-strings of a string. In below C++ code ordered hashmap is used where the time complexity of insert and search is O(Logn). In C++, ordered hashmap is implemented using Red Black Tree.

Step 3: Printing the distinct palindromes and number of such distinct palindromes: 
The last step is to print all values stored in the HashMap (only distinct elements will be hashed due to the property of HashMap). The size of the map gives the number of distinct palindromic continuous sub-strings.

Below is the implementation of the above idea.

Output: 

 Below are 5 palindrome sub-strings
a
aa
aaa
aba
b 

Method 2 :

String length – N

Step 1 : Find all the palindromic sub-strings

        First for every sub-string check if it is palindrome or not using dynamic programming like this – https://www.geeksforgeeks.org/count-palindrome-sub-strings-string/

        Time complexity – O(N²)   and   Space complexity – O(N²)

Step 2 : Remove duplicate palindromes

        For every index starting from index 0 we will use KMP algorithm and check if prefix and suffix is same and is palindrome then we will put 0 the dp array for that suffix sub-string

        Time complexity O(N²)    and   Space complexity O(N) for KMP array

Step 3 : Print the distinct palindromes and number of such palindromes

        For every sub-string check if it is present in dp array (i.e dp[i][j] == true) and print it.

        Time complexity O(N²)   and    Space complexity O(N)

Overall Time complexity – O(N²)

Overall Space complexity – O(N²)

Below is the implementation of the above idea.

a
aba
b
aa
aaa
Total number of distinct palindromes is 5
a
aa
aaa
aaaa
aaaaa
aaaaaa
aaaaaaa
aaaaaaaa
aaaaaaaaa
aaaaaaaaaa
Total number of distinct palindromes is 10

Approach:

This code uses an unordered set to store distinct palindromes and avoids using dynamic programming or the KMP algorithm. It first checks for odd-length palindromes and then even-length palindromes by expanding from each character as a center. Finally, it prints all distinct palindromes and the total count.

aa
aaa
aba
b
a
Total number of distinct palindromes is 5
aaaaaaaaaa
aaaaaaaa
aaaaaa
aaaa
aaaaaaa
aa
aaaaa
aaa
aaaaaaaaa
a
Total number of distinct palindromes is 10

Time complexity: O(N^3)
Space complexity: O(N)

Similar Problem: 
Count All Palindrome Sub-Strings in a String
This article is contributed by Vignesh Narayanan and Sowmya Sampath. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.