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 (lower-case and/or upper-case),

Idea:

Dynamic Programing

``````dp[i][j] = if the substring from i to j is a palindrome = true
dp[i][j] = dp[i+1][j-1] and s[i] === s[j]
base case:
dp[i][i] = true;
dp[i][i+1] = s[i] === s[i+1];``````
• Time complexity : O(n2)
• Space complexity : O(n2)

Solution:

``````var longestPalindrome = function(s) {
let len = s.length;
if (s === null || len === 1) return s;
let dp = Array.from(new Array(len), () => new Array(len));
let res = "";
let max = 0;

for (let j = 0; j < len; j++) {
// remember i <= j
for (let i = 0; i <= j; i++) {
let isSame = s[i] === s[j];

// one and two letters palindromes only check s[i] === s[j]
// more than 2, check subset dp[][] && s[i] === s[j]
dp[i][j] = j - i <= 2 ? isSame : dp[i + 1][j - 1] && isSame;

// any new max palindrome, update max and longest result
if (dp[i][j] && j - i + 1 > max) {
max = j - i + 1;
res = s.substring(i, j + 1);
}
}
}
return res;
}``````