Given a string, find the longest substring that is also a palondrom.
One simple solution is to find reverse of S and then find the longest common substring between S and reverse(s). This is also be the longest palindromic substring. That is,
LongestPalindromicSubStr(S) = LCS(S, reverse(S)).
LCS can be solved by DP in O(n^2) time and O(n^2) space. Look into my previous post on LCS for details implementation of LCS problem using DP.
We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only 2N-1 such centers.
You might be asking why there are 2N-1 but not N centers? The reason is the center of a palindrome can be in between two letters. Such palindromes have even number of letters (such as “abba”) and its center are between the two ‘b’s.
Since expanding a palindrome around its center could take O(N) time, the overall complexity is O(N2).
public static String longestPalindrom(String str){ int n = str.length(); if(n <= 1){ return str; } int l = 0; int h = 0; int start = 0; int maxlen = 1; for(int i = 1; i < n; i++){ //palindrom of even length with center in space between i-1 and i l = i-1; h = i; int len = 0; while(l >= 0 && h <= n-1 && (str.charAt(l) == str.charAt(h))){ len = h-l+1; if(len > maxlen){ start = l; maxlen = len; } l--; h++; } //palindrom of odd length with center at i l = i; h = i; while(l >= 0 && h <= n-1 && (str.charAt(l) == str.charAt(h))){ len = h-l+1; if(len > maxlen){ start = l; maxlen = len; } l--; h++; } } return str.substring(start, start+maxlen); }
There is a linear time solution to this problem using Manacer’s algorithm which I’ll be discussing in another post.
DP solution
The above algorithm actually does some extra computation than O(n^2). We can do dynamic programming to cache some computation.
Let, LeOPT(i,j) be the maximum length of palindromes considering in the input array A from i to j. OPT(i,j) = 2 + OPT(i+1, j-1) if A[i] = A[j], = max (OPT(i,j-1), OPT(i+1,j), otherwise.
public static int longestPalindromDP(String str){ int n = str.length(); int dp[][] = new int[n+1][n+1]; for(int i = 1; i<n; i++){ dp[i][i] = 1; } //find palindrom of each possible length for(int len = 2; len <= n; len++){ //try to get a palindrom of length len starting at each position i for(int i = 1; i <= n-len+1; i++){ //right end position of current palindrom int j = i+len-1; if(str.charAt(i-1) == str.charAt(j-1)){ dp[i][j] = 2+dp[i+1][j-1]; } else{ dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]); } } } return dp[1][n]; }