Skip to content

5. Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/

js
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
  var start = 0
  var end = 0

  for (let i = 0; i < s.length; i++) {
    let len1 = expandAroundCenter(s, i, i)
    let len2 = expandAroundCenter(s, i, i + 1)
    let len = Math.max(len1, len2)

    if (len > end - start) {
      start = i - ((len - 1) / 2 >> 0)
      end = i + (len / 2 >> 0)
    }
  }

  return s.substring(start, end + 1)
}

function expandAroundCenter(s, left, right) {
  while (left >= 0 && right < s.length && s[left] == s[right]) {
    left--
    right++
  }
  return right - left - 1
}
py
class Solution(object):

    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        start, end = 0, 0

        for i in range(len(s)):
            len1 = self.expandAroundCenter(s, i, i)
            len2 = self.expandAroundCenter(s, i, i + 1)
            length = max(len1, len2)
            if length > end - start:
                start = i - (length - 1) // 2
                end = i + length // 2

        return s[start:end + 1]

    def expandAroundCenter(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1
go
func longestPalindrome(s string) string {
	start, end := 0, 0

	for i := 0; i < len(s); i++ {
		len1 := expandAroundCenter(s, i, i)
		len2 := expandAroundCenter(s, i, i+1)
		length := max(len1, len2)

		if length > end-start {
			start = i - (length-1)/2
			end = i + length/2
		}
	}

	return s[start : end+1]
}

func expandAroundCenter(s string, left int, right int) int {
	for left >= 0 && right < len(s) && s[left] == s[right] {
		left--
		right++
	}
	return right - left - 1
}

func max(x int, y int) int {
	if x >= y {
		return x
	}
	return y
}