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 –


Download   Run Code


e l g o oo goog


Download   Run Code


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

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


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

newest oldest most voted
Notify of
Eric Duminil

“The complexity would be exponential.” Nope.

Salman Khan

This is beautiful!


here is the simple code in JAVA