5. Longest Palindromic Substring

Description:

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

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

Example:

Input: "cbbd"
Output: "bb"

Solutions:

First we have to know how to determine if a string is palindromic. There are 2 ways:

1. For string s[0...n], we check if s[0] == s[n-1], s[1] == s[n-2]... until then index i and n-i-1 equals or cross. If all the equations are satisfied, s is palindromic.
2. For string s[0...n], we check from the middle.
   If there is odd number of characters in s, we check if s[n/2-1] == s[n/2+1], s[n/2-2] == s[n/2+2]... until s[0] == s[n-1]. We do not compare s[n/2] with s[n/2] because they are definitely equal. If all the equations are satisfied, s is palindromic. For example, `s = "abcba", in this case,

i    0  1  2  3  4
s    a  b  c  b  a
n = 5, n/2 = 2

Apparently, s[1] == s[3] and s[0] == s[4] are satisfied, so "abcba" is palindromic.
If there is even number of characters in s, we check if s[n/2-1] == s[n/2], s[n/2-2] == s[n/2+1]...until s[0] == s[n-1]. For example, s = "abba", in this case,

i     0  1  2  3
s     a  b  b  a
n = 4, n/2 = 2

Likewise, s[1] == s[2] and s[0] == s[3] are satisfied, so "abba" is palindromic.

Approach 1: Find all substrings and check if it is palindromic [Time Limit Exceeded]

In this approach, we use a nested loop to get all the substrings, then we can use the first method mentioned above to check if it is plindromic.

public class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        String maxsub = "";
        for (int i = 0; i < n; i++) {
            for (int j = n-1; j >= i; j--) { // be careful that j >= i but not j > i or it would return "" if s is "a"
                String sub = s.substring(i, j+1);
                int sublen = j-i+1, maxlen = maxsub.length();
                if (sublen <= maxlen) break;
                if (isPalindrome(sub)) {
                    maxsub = maxlen < sublen ? sub : maxsub;
                }
            }
        }
        return maxsub;
    }
    
    public boolean isPalindrome(String s) {
        int n = s.length();
        if (n == 0 || n == 1) return true;
        int i = 0;
        while (i < n-1-i) { 
            if (s.charAt(i) != s.charAt(n-1-i)) return false;
            i++;
        }
        return true;
    }
}

This approach is too slow because every time we cut out a substring. We can simply use 2 variables to indicate the start and the end of the substring, which would reduce the time cost.

Approach 2: Optimize approach 1 with 2 "indicating pointers"

As mentioned in the last part of Approach 1, two variables can be treated as pointers to indicate the start and the end of the substring. This way we do not need to calls.substring() every time entering in the loop and would save some time.

public class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        int maxstart = 0;
        // the maxend indicates the end position of the substring, 
        // which means if maxend = i, the sub string should  contains
        // i+1 characters, namely s[0...i]
        int maxend = 0;
        for (int i = 0; i < n; i++) {
            for (int j = n-1; j >= i; j--) {
                int sublen = j-i+1, maxlen = maxend - maxstart + 1;
                if (sublen <= maxlen) break;
                if (isPalindrome(s, i, j)) {
                    if (maxlen < sublen) {
                        maxstart = i;
                        maxend = j;
                    }
                }
            }
        }
        return s.substring(maxstart, maxend+1);
    }
    
    public boolean isPalindrome(String s, int start, int end) {
        int i = start, j = end;
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) return false;
            i++;
            j--;
        }
        return true;
    }
}

Approach 3: Extend from every character to find the longest palindromic substring

The idea is simple but it uses another method to find the palindromic substring. From every character, it tries to extend from 2 sides and to see if each pair of characters are the same. Additionally, we need to extend the character in 2 ways: odd length and even length.

public class Solution {
    int lo, maxLen;
    public String longestPalindrome(String s) {
        int n = s.length();
        for (int i = 0; i < n; i++) {
            extendPalindrome(s, i, i); // odd length
            extendPalindrome(s, i, i+1); // even length
        }
        return s.substring(lo, lo+maxLen);
    }
    
    public void extendPalindrome(String s, int j, int k) {
        while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
            j--;
            k++;
        }
        if (maxLen < k-j-1) {
            lo = j+1;
            maxLen = k-j-1;
        }
    }
}

Approach 4: Dynamic programming

dp[i][j] indicates if s[i...j] is a palindromic string. dp[i][j] is true when and only when s[i] == s[j] and s[i+1...j-1] is a palindromic string.

public class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        int start = 0, maxlen = 0;
        boolean[][] dp = new boolean[n][n];
        for (int j = 0; j < n; j++) {
            for (int i = j; i >= 0; i--) {
                // if the window < 3 (j-i<3)
                //    if the window = 2, for example s[2,3,4], then dp[i+1][j-1]=d[2][2] is definitely true
                //    if the window = 1, for example s[3,4], then d[i+1][j-1]=d[4][3], but s[4...3] is senseless
                //    if the window = 0, for example s[0], then d[i+1][j-1]=d[0][-1], out of boudary
               // 
                dp[i][j] = (s.charAt(i) == s.charAt(j)) && (j-i < 3 || dp[i+1][j-1]);
                
                if (dp[i][j] && j-i+1 > maxlen) {
                    start = i;
                    maxlen = j-i+1;
                }
            }
        }
        return s.substring(start, start+maxlen);
    }
    
}

Reference

[1] https://discuss.leetcode.com/topic/23498/very-simple-clean-java-solution/2
[2] https://discuss.leetcode.com/topic/25500/share-my-java-solution-using-dynamic-programming