LeetCode 5. Longest Palindromic Substring (javascript)

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(n²)
• Space complexity : O(n²)

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;
}