code.ashish.me

Atom feed

Recently added: 128 Longest Consecutive Sequence, 347 Top K Frequent Elements, 045 Jump Game 2, 228 Summary Ranges, 219 Contains Duplicate 2

005 Longest Palindrome Substring

/**
 * 
 * Ashish Patel
 * e: ashishsushilPatel@gmail.com
 * w: https://ashish.me
 *
 */

/* 
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"
*/

function longestPalindromeSubstring(value) {
  let startIndex = 0
  let maxLength = 0

  function compareBetween(left, right) {
    while(left >= 0 && right < value.length && value[left] == value[right]){
      const length = right - left + 1
      if(length > maxLength){
        maxLength = length
        startIndex = left
      }
      left = left -1
      right = right + 1
    }
  }

  for (let index = 0; index < value.length; index++) {
    compareBetween(index-1, index+1)
    compareBetween(index, index+1)    
  }
  
  return value.slice(startIndex, startIndex + maxLength)
}

test('longest Palindrome Substring', () => {
  expect(longestPalindromeSubstring('babad')).toEqual('bab')
});

Created 2020-02-23T16:58:11+00:00 · Edit