5-longest-palindromic-substring¶

Description¶

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

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters.

Solution(Python)¶

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)

        if n < 2:
            return s

        maxlen = 1
        start = 0

        for i in range(n):
            low = i - 1
            high = i + 1
            while high < n and s[high] == s[i]:
                high += 1
            while low >= 0 and s[low] == s[i]:
                low -= 1

            while low >= 0 and high < n and s[low] == s[high]:
                low -= 1
                high += 1

            cur_len = high - low - 1

            if cur_len > maxlen:
                maxlen = cur_len
                start = low + 1

        return s[start: start + maxlen]