# Day 19 - Longest Palindromic Substring

## The Problem

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

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`
• `s` consist 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

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`.