Longest Palindromic Substring Problem
Given a string, find the maximum length contiguous substring of it that is also a palindrome. For example, the longest palindromic substring of “bananas” is “anana”, and the longest palindromic substring of “abdcbcdbdcbbc” is “bdcbcdb”.
The problem differs from the problem of finding the longest palindromic subsequence. Unlike subsequences, substrings are required to occupy consecutive positions within the original string.
Note that the longest palindromic substring is not guaranteed to be unique. For example, there is no palindromic substring in a string abracadabra with a length greater than three. Still, there are two palindromic substrings with length three, namely, aca and ada. If multiple longest palindromic substring exists, return any one of them.
The dynamic programming solution for this problem takes O(n2) time and O(n2) space. This post will discuss another approach to solve this problem that doesn’t require any extra space.
The idea is simple and effective – for each character in the given string, consider it the midpoint of a palindrome and expand in both directions to find the maximum length palindrome. For an even length palindrome, consider every adjacent pair of characters as the midpoint.
Following is the C++, Java, and Python implementation of the idea:
C++
|
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 75 76 77 78 79 80 81 82 |
#include <iostream> #include <string> using namespace std; // Expand in both directions of `low` and `high` to find maximum length palindrome string expand(string str, int low, int high) { // run till `str[low.high]` is a palindrome while (low >= 0 && high < str.length() && (str[low] == str[high])) { low--, high++; // Expand in both directions } // return palindromic substring return str.substr(low + 1, high - low - 1); } // Function to find the longest palindromic substring in `O(n²)` time and `O(1)` space string findLongestPalindromicSubstring(string str) { // base case if (str.length() == 0) { return str; } // `max_str` stores the maximum length palindromic substring // found so far string max_str = "", curr_str; // `max_length` stores the maximum length of palindromic // substring found so far int max_length = 0, curr_length; // consider every character of the given string as a midpoint and expand // in both directions to find maximum length palindrome for (int i = 0; i < str.length(); i++) { // find the longest odd length palindrome with `str[i]` as a midpoint curr_str = expand(str, i, i); curr_length = curr_str.length(); // update maximum length palindromic substring if odd length // palindrome has a greater length if (curr_length > max_length) { max_length = curr_length; max_str = curr_str; } // Find the longest even length palindrome with `str[i]` and `str[i+1]` // as midpoints. Note that an even length palindrome has two // midpoints. curr_str = expand(str, i, i + 1); curr_length = curr_str.length(); // update maximum length palindromic substring if even length // palindrome has a greater length if (curr_length > max_length) { max_length = curr_length; max_str = curr_str; } } return max_str; } int main() { string str = "ABDCBCDBDCBBC"; cout << "The longest palindromic substring of " << str << " is " << findLongestPalindromicSubstring(str); return 0; } |
Output:
The longest palindromic substring of ABDCBCDBDCBBC is BDCBCDB
Java
|
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 75 76 77 78 79 80 81 82 83 |
class Main { // Expand in both directions of `low` and `high` to find maximum length palindrome public static String expand(String str, int low, int high) { // expand in both directions while (low >= 0 && high < str.length() && (str.charAt(low) == str.charAt(high))) { low--; high++; } // return palindromic substring return str.substring(low + 1, high); } // Function to find the longest palindromic substring in `O(n²)` time // and `O(1)` space public static String findLongestPalindromicSubstring(String str) { // base case if (str == null || str.length() == 0) { return str; } // `max_str` stores the maximum length palindromic substring // found so far String max_str = "", curr_str; // `max_length` stores the maximum length of palindromic // substring found so far int max_length = 0, curr_length; // consider every character of the given string as a midpoint and expand // in both directions to find maximum length palindrome for (int i = 0; i < str.length(); i++) { // find the longest odd length palindrome with `str[i]` as a midpoint curr_str = expand(str, i, i); curr_length = curr_str.length(); // update maximum length palindromic substring if odd length // palindrome has a greater length if (curr_length > max_length) { max_length = curr_length; max_str = curr_str; } // Find the longest even length palindrome with str[i] and // str[i+1] as midpoints. Note that an even length palindrome // has two midpoints. curr_str = expand(str, i, i + 1); curr_length = curr_str.length(); // update maximum length palindromic substring if even length // palindrome has a greater length if (curr_length > max_length) { max_length = curr_length; max_str = curr_str; } } return max_str; } public static void main(String[] args) { String str = "ABDCBCDBDCBBC"; System.out.println("The longest palindromic substring of " + str + " is " + findLongestPalindromicSubstring(str)); } } |
Output:
The longest palindromic substring of ABDCBCDBDCBBC is BDCBCDB
Python
|
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 |
# Expand in both directions of `low` and `high` to find maximum length palindrome def expand(s, low, high): length = len(s) # expand in both directions while low >= 0 and high < length and s[low] == s[high]: low = low - 1 high = high + 1 # return palindromic substring return s[low + 1:high] # Function to find the longest palindromic substring in `O(n²)` time and `O(1)` space def findLongestPalindromicSubstring(s): # base case if not s: return '' # `max_str` stores the maximum length palindromic substring found so far max_str = '' # `max_length` stores the maximum length of palindromic # substring found so far max_length = 0 # consider every character of the given string as a midpoint and expand # in both directions to find maximum length palindrome for i in range(len(s)): # find the longest odd length palindrome with `s[i]` as a midpoint curr_str = expand(s, i, i) curr_length = len(curr_str) # update maximum length palindromic substring if the odd length # palindrome has a greater length if curr_length > max_length: max_length = curr_length max_str = curr_str # Find the longest even length palindrome with `s[i]` and `s[i+1]` as # midpoints. Note that an even length palindrome has two midpoints. curr_str = expand(s, i, i + 1) curr_length = len(curr_str) # update maximum length palindromic substring if even length # palindrome has a greater length if curr_length > max_length: max_length = curr_length max_str = curr_str return max_str if __name__ == '__main__': s = 'ABDCBCDBDCBBC' print(f'The longest palindromic substring of {s} is', findLongestPalindromicSubstring(s)) |
Output:
The longest palindromic substring of ABDCBCDBDCBBC is BDCBCDB
The time complexity of the above solution is O(n2) and requires O(n) extra space, where n is the length of the input string. Note that O(n) solution is also possible for this problem by using Manacher’s algorithm.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)