Longest Palindromic Substring

Problem

Given a string, return the longest substring that is a palindrome.

Approach

Expand around center for each position. Try both odd-length (single center) and even-length (two-char center) expansions. Track the best start and length.

When to Use

Substring search with symmetry constraint. Related to Manacher's algorithm for O(n).

Complexity

Time	O(n²)
Space	O(1)

Implementation

SolutionTestsChallenge

longest_palindromic_substring

Longest Palindromic Substring — find the longest palindromic substring.

Problem

Given a string, return the longest substring that is a palindrome.

Approach

Expand around center for each position. Try both odd-length (single center) and even-length (two-char center) expansions. Track the best start and length.

When to use

Substring search with symmetry constraint. Related to Manacher's algorithm for O(n).

Complexity

Time: O(n²) Space: O(1)

longest_palindromic_substring

longest_palindromic_substring(s: str) -> str

Return the longest palindromic substring of s.

longest_palindromic_substring("babad") in ("bab", "aba") True longest_palindromic_substring("cbbd") 'bb'

Source code in src/algo/strings/longest_palindromic_substring.py

def longest_palindromic_substring(s: str) -> str:
    """Return the longest palindromic substring of *s*.

    >>> longest_palindromic_substring("babad") in ("bab", "aba")
    True
    >>> longest_palindromic_substring("cbbd")
    'bb'
    """
    if len(s) < 2:
        return s

    start = 0
    max_len = 1

    def _expand(left: int, right: int) -> None:
        nonlocal start, max_len
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        length = right - left - 1
        if length > max_len:
            start = left + 1
            max_len = length

    for i in range(len(s)):
        _expand(i, i)  # odd length
        _expand(i, i + 1)  # even length

    return s[start : start + max_len]

tests/strings/test_longest_palindromic_substring.py

"""Tests for the longest palindromic substring problem."""

from hypothesis import given
from hypothesis import strategies as st

from algo.strings.longest_palindromic_substring import longest_palindromic_substring


class TestLongestPalindromicSubstring:
    def test_odd_length(self) -> None:
        result = longest_palindromic_substring("babad")
        assert result in ("bab", "aba")

    def test_even_length(self) -> None:
        assert longest_palindromic_substring("cbbd") == "bb"

    def test_single_char(self) -> None:
        assert longest_palindromic_substring("a") == "a"

    def test_empty_string(self) -> None:
        assert longest_palindromic_substring("") == ""

    def test_entire_string(self) -> None:
        assert longest_palindromic_substring("racecar") == "racecar"

    def test_no_repeats(self) -> None:
        result = longest_palindromic_substring("abcd")
        assert len(result) == 1

    @given(s=st.text(alphabet="abc", min_size=1, max_size=40))
    def test_result_is_palindrome_and_substring(self, s: str) -> None:
        result = longest_palindromic_substring(s)
        assert result in s
        assert result == result[::-1]

Implement it yourself

Run: just challenge strings longest_palindromic_substring

Then implement the functions to make all tests pass. Use just study strings for watch mode.

Reveal Solution

longest_palindromic_substring

Longest Palindromic Substring — find the longest palindromic substring.

Problem

Given a string, return the longest substring that is a palindrome.

Approach

Expand around center for each position. Try both odd-length (single center) and even-length (two-char center) expansions. Track the best start and length.

When to use

Substring search with symmetry constraint. Related to Manacher's algorithm for O(n).

Complexity

Time: O(n²) Space: O(1)

longest_palindromic_substring

longest_palindromic_substring(s: str) -> str

Return the longest palindromic substring of s.

longest_palindromic_substring("babad") in ("bab", "aba") True longest_palindromic_substring("cbbd") 'bb'

Source code in src/algo/strings/longest_palindromic_substring.py

def longest_palindromic_substring(s: str) -> str:
    """Return the longest palindromic substring of *s*.

    >>> longest_palindromic_substring("babad") in ("bab", "aba")
    True
    >>> longest_palindromic_substring("cbbd")
    'bb'
    """
    if len(s) < 2:
        return s

    start = 0
    max_len = 1

    def _expand(left: int, right: int) -> None:
        nonlocal start, max_len
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        length = right - left - 1
        if length > max_len:
            start = left + 1
            max_len = length

    for i in range(len(s)):
        _expand(i, i)  # odd length
        _expand(i, i + 1)  # even length

    return s[start : start + max_len]