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]

 
1 Star2 Stars3 Stars4 Stars5 Stars (5 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Eric Duminil
Guest

“The complexity would be exponential.” Nope.

Salman Khan
Guest

This is beautiful!

Rishabh Tripathi
Guest

Woow, that’s great. It is the simplest code I ever saw.
Good.

AJ
Guest

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