DEV Community

loading...

Day 19 - Longest Palindromic Substring

ruarfff profile image Ruairí O'Brien ・3 min read

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.
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: s = "cbbd"
Output: "bb"
Enter fullscreen mode Exit fullscreen mode

Example 3:

Input: s = "a"
Output: "a"
Enter fullscreen mode Exit fullscreen mode

Example 4:

Input: s = "ac"
Output: "a"
Enter fullscreen mode Exit fullscreen mode

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters (lower-case and/or upper-case)

Tests

Link to code

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
Enter fullscreen mode Exit fullscreen mode

Solution

Link to code

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
Enter fullscreen mode Exit fullscreen mode

Analysis

Alt Text

Alt Text

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))
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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.

Discussion (0)

pic
Editor guide