Longest Palindromic Substring

String

Current Substring

Center

Left / Right

0 / 0

Longest Palindrome

Length

Found Palindromes

None found yet

Click "Step" or "Play" to start the visualization

Center

Expanding

Palindrome

Longest Found

Python Code - Expand Around Center

                def expand(left, right):
            
                    while left >= 0 and right < n and s[left] == s[right]:
            
                        left -= 1; right += 1
            
                for i in range(n): # each center
            
                    len1 = expand(i, i) # odd-length
            
                    len2 = expand(i, i+1) # even-length
            
                    if max(len1, len2) > max_len: update

Complexity Analysis

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

Time Complexity: O(n²)

Breakdown

Possible centers: 2n - 1 (n single chars + n-1 gaps)
Expansion per center: O(n) worst case
Total: (2n - 1) × O(n) = O(n²)
Best case (all distinct): O(n)

T(n) = Σ expansion(center_i) ≤ (2n-1) × n = O(n²)

Mathematical Intuition

Every palindrome has exactly one center (odd-length: a character, even-length: between characters). By expanding from each center until mismatch, we enumerate all maximal palindromes. The worst case occurs with strings like "aaa...a" where every expansion reaches the boundaries.

Key Insight

Manacher's algorithm achieves O(n) by exploiting palindrome symmetry—if we're inside a known palindrome, we can reuse expansion lengths from the mirrored position.

Space Complexity: O(1)

Breakdown

Center index: single integer
Left/right expansion pointers: two integers
Best palindrome bounds: two integers
No auxiliary arrays or recursion

S(n) = O(1) — fixed number of variables

Mathematical Intuition

Unlike DP approaches that store an n×n table of palindrome states, expand-around-center computes each palindrome on-the-fly. We only track the best result found, not intermediate states. The algorithm is also "online" in that we can process characters incrementally.

Key Insight

The O(n²) DP solution uses O(n²) space for the memoization table. Expand-around-center trades time efficiency (same O(n²)) for optimal O(1) space.