> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# 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](https://leetcode.com/problems/longest-palindromic-substring/description/).

Generate this problem as a practice environment: tested reference solution, 12 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
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](https://github.com/wislertt/leetcode-py/blob/main/leetcode/longest_palindromic_substring/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/longest_palindromic_substring/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
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](/catalog/grind-75), [Grind](/catalog/grind), [Blind 75](/catalog/blind-75), [NeetCode 150](/catalog/neetcode-150), [NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).