Longest Palindromic Substring

Longest Palindromic Substring is a classic string interview problem. It teaches a clean, intuitive technique — expand around the center — that beats the obvious cubic brute force without any fancy data structure.

The slow way first

The obvious idea: generate every substring, check each one for being a palindrome, and keep the longest. There are O(n²) substrings and each palindrome check costs O(n), so this is O(n³) — far too slow for a long string.

The question to ask: what makes a palindrome special? It is symmetric around its center. So instead of testing arbitrary substrings, we can grow palindromes outward from their centers — and there are only a handful of centers to try.

The idea: expand around each center

Every palindrome has a center. For odd-length palindromes (like "aba") the center is a single character; for even-length ones (like "abba") the center sits between two characters. That gives 2n − 1 centers in total.

For each center we set two pointers l and r and march them apart as long as they stay in bounds and s[l] == s[r]. The widest palindrome we ever see is the answer.

Walk through it

Step through the animation. The pointers l and r start together on a center and expand outward. When centered on the a at index 1, they grow to cover "bab" — the longest palindrome in "babad". Other centers are tried too, but none beats it.

Pseudocode

best = ""
for each index c in s:
    for each starting pair (l, r) in [(c, c), (c, c + 1)]:   # odd, then even center
        while l in bounds and r in bounds and s[l] == s[r]:
            if (r - l + 1) is longer than best:
                best = s[l .. r]
            move l left and r right
return best

The Python solution

def longest_palindrome(s):
    best = ""
    for c in range(len(s)):
        for l, r in ((c, c), (c, c + 1)):
            while l >= 0 and r < len(s) and s[l] == s[r]:
                if r - l + 1 > len(best):
                    best = s[l:r + 1]
                l, r = l - 1, r + 1
    return best

• best holds the longest palindrome found so far, starting empty.
• The outer loop walks every index c — each is a potential center.
• The inner for l, r in ((c, c), (c, c + 1)) tries both center types: (c, c) is an odd center, (c, c + 1) is an even center between two chars.
• The while loop is the expansion: as long as both pointers are in bounds and the characters match, the substring is a palindrome.
• Inside, we update best whenever the current palindrome is longer, then step l left and r right to widen it.

Complexity

We spend O(n²) time but only O(1) extra space (ignoring the returned string) — no DP table needed. There is a clever O(n) algorithm (Manacher's), but expand-around-center is the one to reach for in an interview: simple, fast enough, and easy to explain.

When this pattern shows up

Practice