LC 0005 [M] Longest Palindromic Substring - ALawliet/algorithms GitHub Wiki

this is kind of like the idea of sliding window but modified to expanding window from i (like start from the middle)

odd = expand by 1 (i) at a time, even = expand by 2 (i+1) at a time

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(l, r):
            while l >= 0 and r < len(s) and s[l] == s[r]:
                l -=1 ; r += 1
            return s[l+1:r]

        res = ''
        for i in range(len(s)):
            odd = expand(i, i)
            even = expand(i, i+1)
            res = max(res, odd, even, key=len)
        return res
example where even is longest:
i=0 | expand odd = a => a | expand even = ab => 
i=1 | expand odd = b => b | expand even = bb => abba
i=2 | expand odd = b => b | expand even = ba => 
i=3 | expand odd = a => a | expand even = a => 
abba

example where odd is longest:
i=0 | expand odd = r => r | expand even = ra => 
i=1 | expand odd = a => a | expand even = ac => 
i=2 | expand odd = c => c | expand even = ce => 
i=3 | expand odd = e => racecar | expand even = ec => 
i=4 | expand odd = c => c | expand even = ca => 
i=5 | expand odd = a => a | expand even = ar => 
i=6 | expand odd = r => r | expand even = r => 
racecar

# a b b a
#   b

# <-abb-> => b
# <-abba-> => abba

s = 'abba'

def expand(l, r):
    # print('expand', l, r, s[l], s[r])
    while l >= 0 and r < len(s) and s[l] == s[r]:
        l -=1 ; r += 1
    return s[l+1:r]

res = ''
for i in range(len(s)):
    odd = expand(i, i)
    even = expand(i, i + 1)
    res = max(res, odd, even, key=len)
    print(f'i={i} | expand odd = {s[i]} => {odd} | expand even = {s[i:i+1+1]} => {even}')
print(res)

footer

⚠️ **GitHub.com Fallback** ⚠️