5 Longest Palindromic Substring

🔀 Pick One

Given a string s, return the longest palindromic substring in s.

Example1:

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

Example2:

Input: "cbbd"
Output: "bb"

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def longestPalindrome(self, s: str) -> str:
        max_str = ''
        for i in range(len(s)):
            temp = self.check(s, i, i)
            if len(temp) > len(max_str):
                max_str = temp
            temp = self.check(s, i, i+1)
            if len(temp) > len(max_str):
                max_str = temp
        return max_str
        
    def check(self, s: str, i: int, j: int) -> str:
        while i >= 0 and j < len(s) and s[i] == s[j]:
            i -= 1
            j += 1
        return s[i+1:j]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

func longestPalindrome(s string) string {
    if len(s) < 1 {
        return ""
    }
    start := 0
    end := 0
    for i := range s {
        len1 := expandAroundCenter(s, i, i)
        len2 := expandAroundCenter(s, i, i+1)
        lenMax := -1
        if len1 > len2 {
            lenMax = len1
        } else {
            lenMax = len2
        }

        if lenMax > end-start+1 {
            start = i - (lenMax-1)/2
            end = i + lenMax/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
}