Longest palindromic string

Question

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:

<= s.length <= 1000
s consist of only digits and English letters (lower-case and/or upper-case),

Hints

How can we reuse a previously computed palindrome to compute a larger palindrome?
If aba is a palindrome, is xabax and palindrome? Similarly is xabay a palindrome?
Complexity based hint: If we use brute-force and check whether for every start and end position a substring is a palindrome we have O(n^2) start - end pairs and O(n) palindromic checks. Can we reduce the time for palindromic checks to O(1) by reusing some previous computation ?

Solution

/**
  * @param {string} s
  * @return {string}
  */
var longestPalindrome = function(s) {
  const len = s.length;
  const dp = [];
  let i = 0;
  let maxLength = 0;
  let substrStart = 0;

  // All substrings of length 1 are palindromes
  while (i < len) {
    dp[i] = [];
    dp[i][i] = true;
    i++;
  }
  maxLength = 1;

  // All substrings of length 2 are palindromes if both characters are same.
  i = 0;
  while (i < len - 1) {
    if (s[i] == s[i + 1]) {
      dp[i] = dp[i] || [];
      dp[i][i + 1] = true;
      substrStart = i;
      maxLength = 2; // Atleast one palindromic substring of length 2 is found
    }
    i++;
  }
  let substrLength = 3;


  while (substrLength <= len) {
    i = 0;

    while (i < len - substrLength + 1) {
      let j = i + substrLength - 1; // index of the position where a substring of length "substrLength" ends.

      if (s[i] == s[j] && dp[i + 1][j - 1]) {
        dp[i] = dp[i] || [];
        dp[i][j] = true;
        if (substrLength > maxLength) {
          maxLength = substrLength;
          substrStart = i;
        }
      }
      i++;
    }
    substrLength++;
  }

  return s.substr(substrStart, maxLength)
};