The Problem
Given a string
s, return the longest palindromic substring ins.
Example 1:
Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd"
Output: "bb"
Example 3:
Input: s = "a"
Output: "a"
Example 4:
Input: s = "ac"
Output: "a"
Constraints:
1 <= s.length <= 1000-
sconsist of only digits and English letters (lower-case and/or upper-case)
Tests
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
Solution
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[0]
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
Analysis
Commentary
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 aba.
Top comments (0)