Longest Palindromic Substring

Loading...LeetCode

Problem

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"

Pseudocode

- use a function that is able to extend outwards to compare chars
    - in a for loop, use function to cover both odd and even cases
    - e.g. for loop travels to middle of string and finds two palindrome char
        - function extends outwards to assess how long this palindrome is
        - store start and end position of longest palindrome
    - return substring with starting and ending index

Solution

// from solution - does the same thing
var longestPalindrome = function (s) {
  const len = s.length;

  let start = 0;

  let end = 0;

  function extendPalindrome(str, e) {
    while (str >= 0 && e < len && s[str] === s[e]) {
      if (e - str > end - start) [start, end] = [str, e];
      str--;

      e++;
    }
  }

  for (let i = 0; i < len; i++) {
    extendPalindrome(i, i); // for odd length
    extendPalindrome(i, i + 1); // for even length
  }

  return s.slice(start, end + 1);
};

Time and Space Complexity

Time

• What did the code do

• Total -

Space

• What did the code do

• Total -