Longest Palindromic Substring Python Solution

Tested Python solution for LeetCode 5 with 12 pytest cases. Generate a practice environment with lcpy.

LeetCode 5, Medium. Topics: Two Pointers, String, Dynamic Programming. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 12 parametrized pytest cases, and a playground notebook:

lcpy gen -n 5   # by problem number
lcpy gen -s longest_palindromic_substring   # by problem name

​

Problem

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

​

Examples

Input: s = "babad"
Output: "bab"

Explanation: “aba” is also a valid answer.

Input: s = "cbbd"
Output: "bb"

​

Constraints

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(n^2)
    # Space: O(1)
    def longest_palindrome(self, s: str) -> str:
        start = 0
        max_len = 0

        for i in range(len(s)):
            # Odd length palindromes (center at i)
            len1 = self.expand(s, i, i)
            # Even length palindromes (center between i and i+1)
            len2 = self.expand(s, i, i + 1)

            curr_len = max(len1, len2)
            if curr_len > max_len:
                max_len = curr_len
                start = i - (curr_len - 1) // 2

        return s[start : start + max_len]

    @staticmethod
    def expand(s: str, left: int, right: int) -> int:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1


class SolutionManacher:
    # Time: O(n)
    # Space: O(n)
    def longest_palindrome(self, s: str) -> str:
        t = "#".join(f"^{s}$")
        n = len(t)
        p = [0] * n
        center = right = 0
        for i in range(1, n - 1):
            mirror_value = 2 * center - i
            p[i] = min(right - i, p[mirror_value]) if right > i else 0

            while t[i + 1 + p[i]] == t[i - 1 - p[i]]:
                p[i] += 1

            if i + p[i] > right:
                center, right = i, i + p[i]

        max_len = max(p)
        center_index = p.index(max_len)

        # Map back to original string: (center_index - max_len) // 2
        start = (center_index - max_len) // 2
        return s[start : start + max_len]

​

Complexity

Time	Space
O(n^2)	O(1)

​

Tags

Grind 75, Grind, Blind 75, NeetCode 150, NeetCode 250, NeetCode All.