0005. Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring

Description

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

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

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

Constraints:

• 1 <= s.length <= 1000

• s consist of only digits and English letters.

AC1: Central expansion

class Solution {
    public String longestPalindrome(String s) {
        // edge cases
        if (s == null || s.length() <= 1 ) return s;

        // iterate string
        String res = "";
        for (int i = 0; i < s.length() - 1; i++) {
            String s1 = expends(s, i, i);
            String s2 = expends(s, i, i+1);
            String tmp = s1.length() > s2.length() ? s1 : s2;
            res = tmp.length() > res.length() ? tmp : res;
        }

        return res;
    }

    private String expends(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        return s.substring(l+1, r);
    }
}

another version

class Solution {
    private int max = 0;
    private int start = 0;

    public String longestPalindrome(String s) {
        // edge cases
        if (s == null || s.length() <= 1 ) return s;

        // iterate string
        for (int i = 0; i < s.length() - 1; i++) {
            expends(s, i, i);
            expends(s, i, i+1);
        }

        return s.substring(start, start + max);
    }

    private void expends(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }

        if (max < r - l - 1) {
            start = l + 1;
            max = r - l - 1;
        }
    }
}

AC2: DP

public class Solution {
    public static String longestPalindrome(String s) {
        int n = s.length();
        String res = null;
        int palindromeStartsAt = 0, maxLen = 0;

        boolean[][] dp = new boolean[n][n];
        // dp[i][j] indicates whether substring s starting at index i and ending at j is palindrome

        for(int i = n-1; i >= 0; i--) { // keep increasing the possible palindrome string
            for(int j = i; j < n; j++) { // find the max palindrome within this window of (i,j)

                //check if substring between (i,j) is palindrome
                dp[i][j] = (s.charAt(i) == s.charAt(j)) // chars at i and j should match
                           && 
                           ( j-i < 3  // if window is less than or equal to 3, just end chars should match
                             || dp[i+1][j-1]  ); // if window is > 3, substring (i+1, j-1) should be palindrome too

                //update max palindrome string
                if(dp[i][j] && (j-i+1 > maxLen)) {
                    palindromeStartsAt = i;
                    maxLen = j-i+1;
                }
            }
        }
        return s.substring(palindromeStartsAt, palindromeStartsAt+maxLen);
    }
}