LC 5 - Longest Palindromic Substring

Question

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.

Links

Question here and solution here

Solution

concept

For the two pointer solution, we can run the standard palindromic checking twice assuming the longest string could be either even or odd

code

class Solution:
    def longestPalindrome(self, s: str) -> str:
        ans = ""
        ans_len = 0

        def get_palin(l, r):
            nonlocal ans, ans_len
            while l >= 0 and r < len(s) and s[l] == s[r]:
                if r - l + 1 > ans_len:
                    ans_len = r - l + 1
                    ans = s[l:r+1]
                l -= 1
                r += 1
        
        # odd
        for i in range(len(s)):
            l, r = i, i
            get_palin(l,r)

        # even
        for i in range(len(s)):
            l, r = i, i + 1
            get_palin(l,r)
        
        return ans

Complexity

time: $O(n^2)$
space: $O(n)$