Longest Palindromic Substring

The problem description can be found in LeetCode.

Approach

If we think of a way to solve the problem without knowing much about programming, the first method we would probably try is to expand a possible palindrome string from any character (the centre of the string).

For example:

s = "aaa"
      c -> center of the string

We could consider the second a as center and expand the string on both left and right. In this way, we would get the maximum palindrome, which is the string itself.

The example above considers a string with an odd number of characters. What about a string with an even length?

s = "aaaa"
      cc -> centers of the string

In this case, we would have two centers. So, it will be enough to start the pointers at two different positions.

Solution

from typing import Tuple


class Solution:
    def longestPalindrome(self, s: str) -> str:
        max_size = 0
        left = right = 0

        for i in range(len(s)):
            o_left, o_right, o_size = self.get_palindrome(s, i, i)
            if o_size > max_size:
                left, right = o_left, o_right
                max_size = o_size

            e_left, e_right, e_size = self.get_palindrome(s, i, i + 1)
            if e_size > max_size:
                left, right = e_left, e_right
                max_size = e_size

        return s[left : right + 1]

    def get_palindrome(self, s: str, left: int, right: int) -> Tuple[int, int, int]:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1

        return left + 1, right - 1, right - left + 1

Complexity

• Time: $O(n^2)$
• Space: $O(1)$

Where $n$ is the size of the s string.