Day 19 - Longest Palindromic Substring
Tags: leetcode, python, challenge
Published: 2021-01-20 00:41:19

## 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

[Link to code](https://github.com/ruarfff/leetcode-jan-2021)

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

[Link to code](https://github.com/ruarfff/leetcode-jan-2021)

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

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/eogp98nqyul6cpffyfjn.png)

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/92a4m82j9iwh0ua44dkk.png)

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

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

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