Longest Palindromic Substring

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

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

Problem Analysis

Need a boolean do array to record the relationship between the left and right boundary.

dp[i][j] = i equal to the right pointer and j equal to left pointer, true means there is a palindromic string between two boundaries.

Algorithm Analysis

Given a leftLongest and rightLongest integer to track the longest length of the results.

Used a left and right pointers to loop through our string. Right pointer goes forward and left pointer follows the right pointer starting from 0.

Used a boolean variable isInnerParlidrom to check left + 1 and right - 1. (If right - left <= 2 it means the inner string always be Parlidrom)

Check the current characters pointed by these two pointers and the state of the inner word. If the current string is Palindrome, update the left and right longest records.

Time Complexity Analysis - Dynamic Programming

Time: O(n^2)
Space: O(n^2)

Code Implementation

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if(len == 0) return s;
        int leftLongest = 0;
        int rightLongest = 0;
        /* stored the boundry relationship with palindrome */
        boolean[][] isPalindrome = new boolean[len][len];
        
        /* Two pointer for the left and right window */
        for(int right = 1; right < len; right++) {
            for(int left = 0; left < right; left++ ) {
                
                /* See if the inner word is palindrome or if the right and left len smaller than 2 */
                boolean isInnerWordPalindrome = isPalindrome[left + 1][right - 1] || right - left <= 2;
                
                /* Check if the current characeter is the same and the ineer also Palindrome */
                if(s.charAt(left) == s.charAt(right) && isInnerWordPalindrome) {
                    isPalindrome[left][right] = true;
                    
                    /* Update the current leftLongest and rightLongest */
                    if(right - left > rightLongest - leftLongest) {
                        rightLongest = right;
                        leftLongest = left;
                    }
                }
            }
        }
        return s.substring(leftLongest, rightLongest + 1);
    }
}

Follow up - More efficient

The basic idea is to traverse all the palindromes with its pivot range from the first char of string s to the last char of string s (consider both even length and odd length situation). Use StringBuilder to minimize space complexity.

public class Solution {
StringBuilder longest = new StringBuilder("");

public String longestPalindrome(String s) {
    if (s.length() <= 1) return s;
    
    for (int i = 0; i < s.length(); i++) {
        expand(s, longest, i, i); //odd
        expand(s, longest, i, i + 1); //even
    }
    
    return longest.toString();
}

private void expand(String s, StringBuilder longest, int i, int j) {
    while (i >= 0 && j < s.length()) {
        if (s.charAt(i) == s.charAt(j)) {
            if (j - i + 1 > longest.length()) {
                longest.delete(0, longest.length());
                longest.append(s.substring(i, j + 1));
            }
            i--;
            j++;
        }
        else
            break;
    }
}