# LeetCode 5: Longest Palindromic Substring

## Problem Restatement

We are given a string `s`.

We need to return the longest substring that is a palindrome.

A palindrome reads the same forward and backward.

Examples:

```text
"aba"
"racecar"
"bb"
```

All of these are palindromes.

A substring must be contiguous.

For example:

```text
"aceca"
```

is a substring of `"racecar"`.

But:

```text
"rcar"
```

is not contiguous, so it is not a substring.

The problem asks for the substring itself, not its length.

The LeetCode statement allows multiple valid answers if several longest palindromes have the same length. ([leetcode.com](https://leetcode.com/problems/longest-palindromic-substring/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | A string `s` |
| Output | The longest palindromic substring |
| Constraint | `1 <= s.length <= 1000` |
| Characters | English letters and digits |

Example function shape:

```python
def longestPalindrome(s: str) -> str:
    ...
```

## Examples

Example 1:

```text
s = "babad"
```

Possible answers:

```text
"bab"
"aba"
```

Both are correct because both have length `3`.

Example 2:

```text
s = "cbbd"
```

The answer is:

```text
"bb"
```

Example 3:

```text
s = "a"
```

A single character is always a palindrome.

So the answer is:

```text
"a"
```

Example 4:

```text
s = "ac"
```

The longest palindrome has length `1`.

So either:

```text
"a"
```

or:

```text
"c"
```

is valid.

## First Thought: Check Every Substring

One possible approach:

1. Generate every substring.
2. Check whether it is a palindrome.
3. Keep the longest one.

To check whether a string is a palindrome:

```python
sub == sub[::-1]
```

Code:

```python
class Solution:
    def longestPalindrome(self, s: str) -> str:
        best = ""

        for i in range(len(s)):
            for j in range(i, len(s)):
                sub = s[i:j + 1]

                if sub == sub[::-1]:
                    if len(sub) > len(best):
                        best = sub

        return best
```

## Problem With Brute Force

There are many substrings.

For a string of length `n`:

- Number of substrings: `O(n^2)`
- Palindrome check per substring: `O(n)`

Total complexity:

| Metric | Value |
|---|---|
| Time | `O(n^3)` |
| Space | `O(1)` ignoring substring copies |

This becomes too slow for longer strings.

## Key Insight

A palindrome mirrors around its center.

Example:

```text
racecar
   ^
```

The center is:

```text
e
```

Characters expand symmetrically:

```text
c == c
a == a
r == r
```

Another example:

```text
abba
  ^^
```

Even-length palindromes have two center characters.

So every palindrome comes from one of two center types:

| Type | Example |
|---|---|
| Odd length | `"aba"` |
| Even length | `"abba"` |

Instead of checking every substring, we expand outward from every possible center.

## Expand Around Center

Suppose:

```text
s = "babad"
```

Choose center:

```text
"a"
```

Expand left and right:

```text
b a b
```

Still valid.

Expand again:

```text
outside bounds
```

Stop.

We found:

```text
"bab"
```

Now consider even length:

```text
s = "cbbd"
```

Center between the two `b` characters:

```text
b | b
```

Expand outward:

```text
bb
```

Next expansion:

```text
c != d
```

Stop.

We found:

```text
"bb"
```

## Algorithm

For every index `i`:

1. Expand around center `(i, i)` for odd-length palindromes.
2. Expand around center `(i, i + 1)` for even-length palindromes.
3. Keep the longer result.

The expansion process:

- While:
  - indices stay inside bounds
  - and characters match
- Move:
  - left pointer left
  - right pointer right

When expansion stops, the palindrome is the region between them.

## Correctness

Every palindrome has a center.

For odd-length palindromes, the center is one character.

For even-length palindromes, the center is the gap between two characters.

The algorithm explicitly tries both possibilities at every position.

During expansion, the algorithm only continues while:

```text
s[left] == s[right]
```

So the current substring always remains a palindrome.

When expansion stops, one of two things happened:

1. The pointers left the string bounds.
2. The characters no longer matched.

Therefore the largest valid palindrome around that center has already been found.

Since the algorithm checks every possible center, it eventually checks the center of the global longest palindrome.

So the algorithm returns the longest palindromic substring.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2)` | Each center may expand across the string |
| Space | `O(1)` | Only pointers and indices are stored |

This is much faster than the brute-force `O(n^3)` approach.

## Implementation

```python
class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(left: int, right: int) -> str:
            while (
                left >= 0
                and right < len(s)
                and s[left] == s[right]
            ):
                left -= 1
                right += 1

            return s[left + 1:right]

        best = ""

        for i in range(len(s)):
            odd = expand(i, i)

            if len(odd) > len(best):
                best = odd

            even = expand(i, i + 1)

            if len(even) > len(best):
                best = even

        return best
```

## Code Explanation

The helper function:

```python
expand(left, right)
```

tries to grow a palindrome outward.

The loop condition:

```python
s[left] == s[right]
```

ensures the substring stays symmetric.

When the loop ends, the pointers have moved one step too far.

So the correct palindrome is:

```python
s[left + 1:right]
```

We then try every possible center:

```python
for i in range(len(s)):
```

Odd-length center:

```python
expand(i, i)
```

Even-length center:

```python
expand(i, i + 1)
```

Whenever a longer palindrome appears, we update:

```python
best
```

Finally:

```python
return best
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.longestPalindrome("babad") in ["bab", "aba"]
    assert s.longestPalindrome("cbbd") == "bb"
    assert s.longestPalindrome("a") == "a"
    assert s.longestPalindrome("ac") in ["a", "c"]
    assert s.longestPalindrome("racecar") == "racecar"
    assert s.longestPalindrome("aaaa") == "aaaa"
    assert s.longestPalindrome("abcda") in ["a", "b", "c", "d"]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `"babad"` | Multiple valid answers |
| `"cbbd"` | Even-length palindrome |
| `"a"` | Single-character string |
| `"ac"` | No palindrome longer than 1 |
| `"racecar"` | Whole string is palindrome |
| `"aaaa"` | Repeated characters |
| `"abcda"` | Only length-1 palindromes exist |