Longest palindromic substring in O(n^2) time

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];
}