# 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

```java
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

```java
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

```java
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);
    }
}
```
