[Leetcode] 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.

A very classical problem. The most naive way is to enumerate all substring and then check if each string is a valid palindrome. This would give O(n^3) time complexity. A better way is to start from a character as the center and expand to left and right to see the longest palindrome we could obtain. We need to check two cases: both even length and odd length. This would give O(n^2) time complexity.

    public String longestPalindrome(String s) {
        int n = s.length();
        if(n == 0)
            return s; // corner case
        int ma = 0;
        int mai = 0, maj = 0;
        for(int i = 0; i < n; i++) { // case 1 odd
            int left = i, right = i;
            while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                left--; right++;
            }
            if(ma < right - left - 1) {
                ma = right - left - 1;
                mai = left + 1;
                maj = right - 1;
            }
        }
        for(int i = 0; i < n-1; i++) { // case 2 even
            int left = i, right = i+1;
            while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                left--; right++;
            }
            if(ma < right - left - 1) {
                ma = right - left - 1;
                mai = left + 1;
                maj = right - 1;
            }
        }
        return s.substring(mai, maj+1);
    }

Another way is to use DP to solve this problem. However, the time complexity is still O(n^2) and space complexity is O(n^2), too. The steps are as follow:

• We use dp[i][j] to represent whether s[i...j] is a valid palindrome or not.

1. if i == j, then dp[i][j] = true.
2. if i+1 == j and s[i] == s[j], dp[i][j] = true.
3. otherwise, only if dp[i+1][j-1] == true and s[i] == s[j], dp[i][j] = true.

• During the process, whenever we find a new valid palindrome, we update the current max and record the index

    public String longestPalindrome(String s) {
        int n = s.length();
        if(n == 0)
            return s; // corner case
        boolean[][] dp = new boolean[n][n];
        int ma = 0;
        int mai = 0, maj = 0; // index of the longest palindrome string
        for(int i = n-1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                if(i == j) { // case 1
                    dp[i][j] = true;
                    if(ma < j-i+1) {
                        ma = j-i+1;
                        mai = i; maj = j;
                    }
                }
                else if(i+1 == j) { // case 2
                    if(s.charAt(i) == s.charAt(j)) {
                        dp[i][j] = true;
                        if(ma < j-i+1) {
                            ma = j-i+1;
                            mai = i; maj = j;
                        }
                    }
                    else
                        dp[i][j] = false;
                }
                else { // case 3
                    if(s.charAt(i) == s.charAt(j) && dp[i+1][j-1] == true) {
                        dp[i][j] = true;
                        if(ma < j-i+1) {
                            ma = j-i+1;
                            mai = i; maj = j;
                        }
                    }
                    else
                        dp[i][j] = false;
                }
            }
        }
        return s.substring(mai, maj+1);
    }