Given a string
s, return the longest palindromic substring in
Input: s = "babad" Output: "bab" Note: "aba" is also a valid answer.
Input: s = "cbbd" Output: "bb"
Input: s = "a" Output: "a"
Input: s = "ac" Output: "a"
1 <= s.length <= 1000
sconsist of only digits and English letters (lower-case and/or upper-case)
import pytest from .Day19_LongestPalindromicSubstring import Solution s = Solution() @pytest.mark.parametrize( "string,expected", [("babad", "bab"), ("cbbd", "bb"), ("a", "a"), ("ac", "a"), ("bb", "bb")], ) def test_longest_palindrome(string, expected): assert s.longestPalindrome(string) == expected
class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) # If we have a string with all single letters this will actually be the answer ans = s for i in range(n): # We need to scan i and i+1 to account for palindromes with multiple letters from the middle e.g. bb or abba dist = max(self.scan(s, n, i, i), self.scan(s, n, i, i + 1)) # If we discovered a palindrome longer than the current answer if dist > len(ans): # set our answer to a substring using dist to calculate the appropriate indices ans = s[i - (dist - 1) // 2 : (i + dist // 2) + 1] return ans def scan(self, s: str, n: int, l: int, r: int) -> int: while l >= 0 and r < n and s[l] == s[r]: l -= 1 r += 1 return r - l - 1
Hopefully the comments in the code explain the solution well enough. I felt there were 2 ways to possibly do it. One is to check palindromes outside in. The other is inside out. Inside out was more intuitive to me. It was also easier to code and seems to perform well.
One bit that caught me for a while which might be worth talking about.
dist = max(self.scan(s, n, i, i), self.scan(s, n, i, i + 1))
Initially I had
dist = self.scan(s, n, i, i). I struggled for a while trying to figure out why it worked in some cases and not in others. I turned out to fail when there were 2 letters together in the middle of a palindrome.
For example, take 'bb'. Calling
scan('bb', 2, 0, 0).
Let's replace the variables with the values to see what it looks like:
while 0 >= 0 and 0 < 2 and 'b' == 'b': 0 -= 1 0 += 1 return 1 - (-1) - 1 # The result is 1
We get 1 back but obviously it should be 2 since 'bb' is a palindrome.
If we push the right pointer up 1 we can fix that. Calling
scan('bb', 2, 0, 1).
while 0 >= 0 and 1 < 2 and 'b' == 'b': 0 -= 1 1 += 1 return 2 - (-1) - 1 # The result is 2 (minus + a minus is a plus)
Given those 2 example for 'bb', we are looking at
max(1, 2) which gives us 2 and is correct in this case.
Why not always just call
scan(s, n, i, i + 1)? That won't work for the case where letters are 1 letter in the middle of matching letters like