Center Expansion (Palindromes & Symmetry)

Center expansion grows a palindrome outward from a middle pivot. Try each index as the center for odd length palindromes, and each gap between characters for even length. It is the intuitive core before learning Manacher’s algorithm.

Why this shows up in the real world

DNA palindrome regions hint at structure; biologists scan with expansion-like windows. UI symmetry tools in graphics editors mirror strokes around a center line—same mental picture.

Core idea (explained for students)

Function expand(lo, hi) while characters match and indices stay in bounds; count length hi-lo-1. Run for lo=hi=i and lo=i, hi=i+1. Track the maximum length slice.

Try this in Python

def longest_palindrome(s: str) -> str:

    def expand(l: int, r: int) -> tuple[int, int]:
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return l + 1, r - 1

    start, end = 0, 0
    for i in range(len(s)):
        for l, r in (expand(i, i), expand(i, i + 1)):
            if r - l > end - start:
                start, end = l, r
    return s[start : end + 1]


print(longest_palindrome("babad"))

Common mistakes

• Off-by-one when returning substring indices after expansion.
• O(n²) time on adversarial strings—acceptable for teaching sizes; production may need faster methods.

Key takeaways

• Always implement both centers—odd and even.
• Reuse expand to avoid duplicated loops.