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 O(n3).

 
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.

 
Below is C++ and Java implementation of the idea –

C++

Download   Run Code

Output:

e l g o oo goog

Java

Download   Run Code

Output:

[oo, goog, e, g, l, o]

 
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 🙂

Get great deals at Amazon




Leave a Reply

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

“The complexity would be exponential.” Nope.

AJ
Guest

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

wpDiscuz