Longest Palindromic Substring

Given a string, find maximum-length contiguous substring of it that is also a palindrome. For example, the longest palindromic substring of “bananas” is “anana” and longest palindromic substring of “abdcbcdbdcbbc” is “bdcbcdb”.


Note that the longest palindromic substring is not guaranteed to be unique. For example, in the string abracadabra, there is no palindromic substring with length greater than three, but there are two palindromic substrings with length three, namely, aca and ada. If multiple longest palindromic substring exists, return any one of them.

Dynamic Programming solution for this problem takes O(n2) time and O(n2) space. In this post, we will discuss another approach to solve this problem that doesn’t require any extra space.

The idea is very simple and effective. For each character in the given string, we consider it as mid point of a palindrome and expand in both directions to find maximum length palindrome. For even length palindrome, we consider every adjacent pair of characters as mid point.

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


Download   Run Code


Download   Run Code


Longest Palindromic Substring of ABDCBCDBDCBBC is BDCBCDB

The time complexity of above solution is O(n2) and auxiliary space used by the program is O(1). Note that O(n) solution is also possible for this problem. We can achieve linear complexity by using Manacher’s algorithm. We will discuss Manacher’s algorithm in a separate post.

1 Star2 Stars3 Stars4 Stars5 Stars (4 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

Thanks for the explanation!

Isn’t the space complexity O(n) here as the function expand creates a string of maximum size n (str:substr makes a copy of the substring of interest).

If I am right, this could be reduced to O(1) by returning low and high instead of the palindrome in expand. (The final palindrome can be reconstructed using low, midpoint and high).