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:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

Solution:

Method 1:

At any point, we can go left and right with the same pace and check how long this palindrome string can be.

We go through the string and start from each character and do the check.

The time complexity is O(n²) and space complexity is O(1).



Code:

public class Solution {
    public String longestPalindrome(String s) {
        String max = "";
        for (int i = 0; i < s.length(); i++) {
            String odd = extend(s, i, i);
            String even = extend(s, i, i + 1);
            if (odd.length() > max.length()) {
                max = odd;
            }
            if (even.length() > max.length()) {
                max = even;
            }
        }
        return max;
    }
    
    public String extend(String s, int i, int j) {
        while (i >= 0 && j < s.length()) {
            if (s.charAt(i) != s.charAt(j)) {
                break;
            }
            i--;
            j++;
        }
        return s.substring(i + 1, j);
    }
}

Method 2: DP

We use dp[i][j] to denote whether s_i,j is palindrome.

If s_i+1,j-1 is palindrome and s_i == s_j, we say s_i,j is palindrome.

Both time complexity and space complexity are O(n²).



Code:

public class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        String max = null;
        
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                dp[i][j] = (s.charAt(i) == s.charAt(j)) && (j - i < 3 || dp[i + 1][j - 1]);
                if (dp[i][j] && (max == null || max.length() < j - i + 1)) {
                    max = s.substring(i, j + 1);
                }
            }
        }
        return max;
    }
}