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”.

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.

We have discussed Dynamic Programming solution to solve this problem that takes O(n^{2}) time and O(n^{2}) 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.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
#include <iostream> using namespace std; // expand in both directions of low and high to find // maximum length palindrome string expand(string str, int low, int high) { int len = str.length(); // run till str[low.high] is a palindrome while (low >= 0 && high < len && (str[low] == str[high])) low--, high++; // expand in both directions // return palindromic substring return str.substr(low + 1, high - low - 1); } // Function to find Longest Palindromic Substring in O(n^2) time // and O(1) space string LongestPalindromicSubstring(string str, int len) { // max_str stores the maximum length palindromic substring // found so far string max_str = "", curr_str; // max_length stores the length of maximum length palindromic // substring found so far int max_length = 0, curr_length; // consider every character of given string as mid points and expand // in its both directions to find maximum length palindrome for (int i = 0; i < len; i++) { // find a longest odd length palindrome with str[i] as mid point curr_str = expand(str, i, i); curr_length = curr_str.length(); // update maximum length palindromic substring if odd length // palindrome has greater length if (curr_length > max_length) { max_length = curr_length; max_str = curr_str; } // find a longest even length palindrome with str[i] and str[i+1] // as mid points. Note that an even length palindrome has two // mid points curr_str = expand(str, i, i + 1); curr_length = curr_str.length(); // update maximum length palindromic substring if even length // palindrome has greater length if (curr_length > max_length) { max_length = curr_length; max_str = curr_str; } } return max_str; } // main function int main() { string str = "ABDCBCDBDCBBC"; cout << "Longest Palindromic Substring of " << str << " is " << LongestPalindromicSubstring(str, str.length() - 1); return 0; } |

**Output: **

Longest Palindromic Substring of ABDCBCDBDCBBC is BDCBCDB

The time complexity of above solution is O(n^{2}) 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 seperate post.

**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

Hello,

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).

Best