Longest Palindromic Substring

mediumTests passed 2026-11-11v1.0.0
TC: O(N^2)|SC: O(1)
1D DPStringsOriginal Statement (leetcode).md

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

There are `2N - 1` centers; expanding each is bounded by O(N) character comparisons with zero 2D DP table.

3. Minimal Idiomatic Code

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]

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.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Decode Ways (O(N))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.