Skip to main content

< Back to Data Structures and Algorithms

LeetCode 5 · Strings

Longest Palindromic Substring

The longest stretch that reads the same both ways, expanding out from every letter and every gap between letters.

Step through it

Examples
Edge cases
s
  1. b0
  2. a1
  3. b2
  4. a3
  5. d4

Step 0 of 16

Output

Running… play or step to the end.

The code

/**
 * Finds and returns the longest panindrome substring (eg. 'abba' in 'babbad')
 *
 * @param {string} s // the string input
 * @return {string} // the longest palindrome substring
 */
 const longestPalindrome = s => {
  // when the string is empty, return the longest palindrome, which is an empty string
  if (!s || s.length < 1) return ''
  
  // the boundaries which we grab a final substring at the end to return from
  let start = 0
  let end = 0
  
  // O(n) loop
  for (let i=0; i < s.length; i++) {
      // Get the longest palindrome for (i) in the cases where the middle of the string is:
      // An odd number (eg. 'racecar'). Left and right are the same index
      let len1 = expandFromMiddle(s, i, i)
      // An even number (eg. 'abba'). Left and right are different indexes
      let len2 = expandFromMiddle(s, i, i+1)
      // The maximum value between the two calculated substring lengths
      const len = Math.max(len1, len2)
      
      // Found a longer palindromic substring.
      if (len > end - start) {
          // i is the center of our substring.
          // start/end boundaries are half of the palindrome length from i.
          start = i - Math.floor((len - 1) / 2)
          end = i + Math.floor(len / 2)
      }        
  }
  
  return s.substring(start, end + 1)
}

/**
* Find and return the length of the longest palindromic substring 
* after expanding out from the middle
*
* @param {string} s // the string input
* @param {int} left // the starting indicy
* @param {int} right // the ending incidy
* @returns {int} // the length of the longest palindromic substring
*/
const expandFromMiddle = (s, left, right) => {
  // There's no palindromic substring to return
  if (!s || left > right) return 0
  
  // O(n) loop
  // Expand the boundaries of the palindromic substring
  while (left >= 0 && right < s.length &&
         s[left] === s[right]
  ) {
      left--
      right++
  }
  
  // higher value - lower value - 1 because we're dealing with 0 based indicies
  return right - left - 1
}

View it on GitHub (opens in a new tab)