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

Example 1:

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

Example 2:

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

Strategy #

Dynamic Programming and Expand around Center

1. We can expand from the center for each letter in the string. If a character matches, we expand further outwards using two pointers.
2. We do this 2n - 1 times. Because we need to look for both odd and even strings.

Patterns #

• Two Pointers
• Expand from Center
• Dynamic Programming

Code #

const longestPalindrome = (s) => {
  let maxLen = 0;
  let maxString = "";

  for (let i = 0; i < s.length; i++) {
    // odd
    let l = i;
    let r = i;
    while (l >= 0 && r < s.length && s[l] === s[r]) {
      if (r - l + 1 > maxLen) {
        maxLen = r - l + 1;
        maxString = s.substring(l, r + 1);
      }

      l--;
      r++;
    }

    //even
    l = i;
    r = i + 1;
    while (l >= 0 && r < s.length && s[l] === s[r]) {
      if (r - l + 1 > maxLen) {
        maxLen = r - l + 1;
        maxString = s.substring(l, r + 1);
      }

      l--;
      r++;
    }
  }

  return maxString;
};

Big-O #

Brute Force: O(n^3). n^2 to go through every possible substring. And n, to verify the palindrome

Optimal: O(n^2) and Space O(1)

Video #