0005 - Longest Palindromic Substring

0005 - Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

Examples

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

Input: s = "cbbd" Output: "bb"

Input: s = "a" Output: "a"

Input: s = "ac" Output: "a"

Constraints

1 <= s.length <= 1000 s consist of only digits and English letters.

Java Solution

Dynammic Programming

class Solution {
    public String longestPalindrome(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        String ans = "";
        for(int g = 0; g < dp.length; g++){
            for(int i = 0, j = g; j < dp.length; i++, j++){
                if(g == 0)
                    dp[i][j] = true;
                else if(g == 1){
                    if(s.charAt(i) == s.charAt(j))
                        dp[i][j] = true;
                }else{
                    if(dp[i+1][j-1] == true && s.charAt(i) == s.charAt(j))
                        dp[i][j] = true;
                }
                if(dp[i][j] == true)
                    ans = s.substring(i, j+1);
            }
        }
        return ans;
    }
}

Expand Around Center

class Solution {
    public String longestPalindrome(String s) {
        if( s == null || s.length() < 1) return "";
        int start = 0;
        int end = 0;
        for(int i = 0; i < s.length(); i++) {
            int oddLength = expandAroundCenter(s, i, i);
            int evenLength = expandAroundCenter(s, i, i+1);
            int maxLength = Math.max(oddLength, evenLength);
            
            if(maxLength > end-start) {
                start = i - (maxLength - 1) / 2;
                end = i + maxLength / 2;
            }
        }
        return s.substring(start, end+1);
        
    }
    
    private int expandAroundCenter(String s, int left, int right) {
        int L = left, R = right;
        while(L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return R - L - 1;
    }
}