0005: Longest Palindromic Substring

Problem Statement

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.

Code Solution

class Solution:
    
    def expand(self, s, lx, rx):
        while lx >= 0 and rx <= len(s) - 1 and  s[lx] == s[rx]:
            lx = lx - 1
            rx = rx + 1
        return s[1 + lx:rx]
        
    def longestPalindrome(self, s: str) -> str:
        N = len(s)
        
        cmax = ""
        for ix in range(N):
            if ix != 0:
                cmax = max(cmax, self.expand(s, ix, ix - 1), key=len)
            cmax = max(cmax, self.expand(s, ix, ix), key=len)
        return cmax