Skip to content

5. Longest Palindromic Substring

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

c++
class Solution {
public:
    string longestPalindrome(string s) {
        int start = 0, end = 0;

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

            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substr(start, end - start + 1);
    }

    int expandAroundCenter(string& s, int left, int right) {
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            left--;
            right++;
        }
        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
}
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