Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Solution:

Define P[ i, j ] ← true if the substring Si ... Sj is a palindrome, otherwise false. Therefore,

P[ i, j ] ← ( P[ i+1, j-1 ] and Si = Sj )

The base cases are:

P[ i, i ]←true

P[ i, i+1 ] ← ( Si = Si+1 )

O(n2) runtime, O(1) space – Simpler solution: 

A palindrome can be expanded from its center, and there are only 2n – 1 (n number as center, and n-1 center between two letters) such centers. 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((2*n-1)*n) = O(n2). Space complexity is O(1).

public class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length() == 0)
            return null;
        
        int start = 0, end = 0;
        
        for(int i = 0; i < s.length(); i++) {
            int len1 = helper(s, i, i); //get longest palindrome with center of i
            int len2 = helper(s, i, i + 1); //get longest palindrome with center between i, i+1
            int len = Math.max(len1, len2);
            
            if(len > end - start) { //replace with the longest palindrom substring
                end = i + len / 2;
                start = i - (len - 1) / 2;
            }
        }
        return s.substring(start, end + 1);
    }
    
    public int helper(String s, int left, int right) {
        while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
        
}