5. Longest Palindromic Substring

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/longest-palindromic-substring
• topics: String Manipulation, Dynamic Programming

Description

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

Idea

• Bruteforce, consider every character as center of possible polyndrome

Code

Bruteforce

class Solution:
    def longestPalindrome(self, s: str) -> str:
        ans = s[0]
        for c in range(1, len(s)):
            t = 0
            while c-t > 0 and c+t < (len(s)-1) and s[c-t-1] == s[c+t+1]:
                t += 1
            if len(ans) < 1 + t * 2:
                ans = s[c-t:c+t+1]
 
            t = 0
            while c-t > 0 and c+t < len(s) and s[c-t-1] == s[c+t]:
                t += 1
            if len(ans) < t * 2:
                ans = s[c-t:c+t]
        return ans