# Longest Palindromic Substring

- **Canonical ID**: `longest-palindromic-substring`
- **Canonical URL**: https://dsacheatsheet.com/problems/longest-palindromic-substring
- **Difficulty**: medium
- **Patterns**: 1D DP, Strings
- **Version**: 1.0.0 (verified 2026-11-11T21:20:00Z)
- **Original Problem**: https://leetcode.com/problems/longest-palindromic-substring/

## 1. Core Invariant / The Trick

Expand outward from every odd (`(i, i)`) and even (`(i, i + 1)`) center in O(1) extra space, tracking `[bestStart, bestLen]` rather than allocating substrings on every expansion.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N^2)`
- **Space Complexity**: `O(1)`
- **Proof**: There are `2N - 1` centers; expanding each is bounded by O(N) character comparisons with zero 2D DP table.

## 3. Minimal Idiomatic Code

### Python
```python
def longestPalindrome(s: str) -> str:
    start = best_len = 0
    def expand(l: int, r: int):
        nonlocal start, best_len
        while l >= 0 and r < len(s) and s[l] == s[r]:
            if r - l + 1 > best_len:
                start, best_len = l, r - l + 1
            l -= 1
            r += 1
    for i in range(len(s)):
        expand(i, i)
        expand(i, i + 1)
    return s[start:start + best_len]
```

### TypeScript
```typescript
export function longestPalindrome(s: string): string {
  let start = 0, bestLen = 0;
  const expand = (l: number, r: number) => {
    while (l >= 0 && r < s.length && s[l] === s[r]) {
      if (r - l + 1 > bestLen) { start = l; bestLen = r - l + 1; }
      l--; r++;
    }
  };
  for (let i = 0; i < s.length; i++) {
    expand(i, i);
    expand(i, i + 1);
  }
  return s.slice(start, start + bestLen);
}
```

### C++
```cpp
string longestPalindrome(string s) {
    int st = 0, best = 0, n = s.size();
    auto expand = [&](int l, int r) {
        while (l >= 0 && r < n && s[l] == s[r]) {
            if (r - l + 1 > best) { st = l; best = r - l + 1; }
            l--; r++;
        }
    };
    for (int i = 0; i < n; ++i) { expand(i, i); expand(i, i + 1); }
    return s.substr(st, best);
}
```

### Java
```java
String longestPalindrome(String s) {
    int st = 0, best = 0;
    for (int i = 0; i < s.length(); i++) {
        for (int r : new int[]{i, i + 1}) {
            int l = i, ri = r;
            while (l >= 0 && ri < s.length() && s.charAt(l) == s.charAt(ri)) {
                if (ri - l + 1 > best) { st = l; best = ri - l + 1; }
                l--; ri++;
            }
        }
    }
    return s.substring(st, st + best);
}
```

### Go
```go
func longestPalindrome(s string) string {
    st, best := 0, 0
    expand := func(l, r int) {
        for l >= 0 && r < len(s) && s[l] == s[r] {
            if r-l+1 > best { st, best = l, r-l+1 }
            l--; r++
        }
    }
    for i := 0; i < len(s); i++ { expand(i, i); expand(i, i+1) }
    return s[st : st+best]
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Only checking odd centers `(i, i)` misses even-length palindromes like `"bb"`.
- Slicing substrings inside the inner `while` loop allocates O(N^3) string garbage; slice only once at `return`.

### Follow-ups
- Manacher’s algorithm achieves O(N) time and space using center-mirror radius reuse.