Skip to content

5. Longest Palindromic Substring

Difficulty Topics

Description

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

A string is called a palindrome string if the reverse of that string is the same as the original string.

 

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

longest-palindromic-substring.py
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n == 1: return s

        def pal(i, j):
            while i >= 0 and j < n and s[i] == s[j]:
                i -= 1
                j += 1

            i += 1
            j -= 1

            return s[i : j + 1]

        res = ''
        for i in range(n - 1):
            res = max(res, pal(i, i), pal(i, i + 1), key = len)

        return res