Find all Possible Palindromic Substrings in a String

Given a string, find all possible palindromic substrings in it.

 

For example,


Input:  str = google

Output: e l g o oo goog

 


 

A simple solution would be to generate all substrings of the given string and print substrings that are palindrome. The complexity of this solution would be exponential.
 

We can solve this problem in O(n2) time and O(1) space. The idea is inspired from Longest Palindromic Substring problem. For each character in the given string, we consider it as mid point of a palindrome and expand in both directions to find all palindromes that have it as mid-point. For even length palindrome, we consider every adjacent pair of characters as mid point. We use a set to store all unique palindromic substrings.

 
C++ implementation –
 

Download   Run Code

Output:

e l g o oo goog

 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
AJ
Guest

here is the simple code in JAVA
https://stackoverflow.com/a/46752568/8778562

wpDiscuz