Introduction

Finding the longest palindromic substring is a classic interview and production coding problem. The brute-force approach is simple but slow for long strings. A center-expansion algorithm gives strong performance with straightforward implementation.

Understand the Core Idea

A palindrome reads the same forward and backward. Every palindrome has a center, either one character for odd length or a gap between two characters for even length. Expand from each center while characters match.

This avoids testing every possible substring directly.

Efficient Center Expansion Implementation

The following Python function runs in quadratic time and constant extra space.

1def longest_palindrome(s: str) -> str:
2    if not s:
3        return ""
4
5    def expand(left: int, right: int) -> tuple[int, int]:
6        while left >= 0 and right < len(s) and s[left] == s[right]:
7            left -= 1
8            right += 1
9        return left + 1, right - 1
10
11    best_l, best_r = 0, 0
12
13    for i in range(len(s)):
14        l1, r1 = expand(i, i)       # odd length
15        l2, r2 = expand(i, i + 1)   # even length
16
17        if r1 - l1 > best_r - best_l:
18            best_l, best_r = l1, r1
19        if r2 - l2 > best_r - best_l:
20            best_l, best_r = l2, r2
21
22    return s[best_l:best_r + 1]
23
24
25print(longest_palindrome("babad"))
26print(longest_palindrome("cbbd"))

This solution balances clarity and performance for most practical inputs.

Testing with Representative Cases

Always validate both odd and even palindrome cases, plus empty and single-character input.

1def run_tests():
2    cases = [
3        ("", ""),
4        ("a", "a"),
5        ("babad", "bab"),
6        ("cbbd", "bb"),
7        ("forgeeksskeegfor", "geeksskeeg"),
8    ]
9
10    for text, expected in cases:
11        got = longest_palindrome(text)
12        if len(got) != len(expected):
13            raise AssertionError(f"fail for {text}: got {got}")
14
15run_tests()

For ambiguous outputs like babad, aba is also valid. Length checks are often more robust than exact string checks.

Complexity and Alternatives

Center expansion runs in quadratic time and constant extra space. For very large strings where performance is critical, Manacher algorithm achieves linear time but is harder to implement and maintain.

In production, center expansion is often the best tradeoff unless profiling proves otherwise.

Dynamic Programming Alternative

Another common method uses dynamic programming to mark whether s[i:j] is a palindrome. It is easier to reason about for some developers, though it uses more memory.

1def longest_palindrome_dp(s: str) -> str:
2    n = len(s)
3    if n == 0:
4        return ""
5
6    dp = [[False] * n for _ in range(n)]
7    start = 0
8    max_len = 1
9
10    for i in range(n):
11        dp[i][i] = True
12
13    for length in range(2, n + 1):
14        for i in range(n - length + 1):
15            j = i + length - 1
16            if s[i] == s[j] and (length == 2 or dp[i + 1][j - 1]):
17                dp[i][j] = True
18                if length > max_len:
19                    start = i
20                    max_len = length
21
22    return s[start:start + max_len]

This approach is useful for educational contexts and for verifying center-expansion implementations.

Benchmarking Different Approaches

Benchmarking helps choose implementation based on input size and runtime constraints.

1import random
2import string
3import time
4
5text = ''.join(random.choice(string.ascii_lowercase) for _ in range(2000))
6
7t0 = time.time()
8_ = longest_palindrome(text)
9t1 = time.time()
10
11_ = longest_palindrome_dp(text)
12t2 = time.time()
13
14print("center:", t1 - t0)
15print("dp:", t2 - t1)

Real measurements often show center expansion as the best balance for typical workloads.

Production Considerations

If this function is used in user-facing APIs, add input size guards and timeout strategy for very large strings. Document complexity and expected behavior for ambiguous outputs. Clear contracts reduce debugging overhead later.

Common Pitfalls

• Handling only odd-length centers and missing even-length palindromes.
• Returning indices incorrectly after expansion loop exits.
• Using full substring reversal checks in nested loops and creating cubic time behavior.
• Writing tests that assume one unique answer when multiple valid outputs exist.

Summary

• Expand around each character and each gap to find palindromes efficiently.
• Track best left and right indices during iteration.
• Test odd and even cases to avoid edge-case bugs.
• Use linear-time alternatives only when proven necessary.