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 longestPalindrome(self, s):
        N = len(s)
        cmax = 0
        output = ""
        for ix in range(N):
            lx = rx = ix
            while lx >= 0 and rx < N and s[lx] == s[rx]:
                if cmax < rx - lx + 1:
                    output = s[lx:1 + rx]
                    cmax = rx - lx + 1
                lx = lx - 1
                rx = rx + 1
        for ix in range(N - 1):
            lx = ix
            rx = ix + 1
            while lx >= 0 and rx < N and s[lx] == s[rx]:
                if cmax < rx - lx + 1:
                    output = s[lx:1 + rx]
                    cmax = rx - lx + 1
                lx = lx - 1
                rx = rx + 1        
        return output