Longest Palindromic Substring — Solution

Problem

Given a string, find the longest contiguous substring that reads the same forwards and backwards. Unlike a palindromic subsequence, characters must be consecutive — you cannot skip positions.

Example:

• Input: s = "babad"
• Output: "bab" (or "aba" — both are valid)
• Explanation: Both "bab" and "aba" are length-3 palindromes; the full string "babad" is not a palindrome.

Counter-example: s = "cbbd" — "b" and "bb" are palindromes, "cbbd" is not; the answer is "bb" with length 2, not "cbd" (which skips a character and is not a substring anyway).

Intuition

Every palindrome has a center — either a single character (odd length, e.g., "aba") or two adjacent matching characters (even length, e.g., "abba"). Rather than checking all O(n²) substrings and verifying each one, we can try expanding outward from each of the 2n−1 possible centers. As soon as the characters on both sides stop matching, we stop. This runs in O(n²) time but uses only O(1) extra space, and it's fast in practice because most expansions terminate quickly.

Solution — Expand Around Center

For each possible center in the string, grow a window outward in both directions as long as the characters match. Track the start and length of the longest palindrome seen across all centers.

Steps:

1. Initialize best_start = 0 and best_length = 1 to handle the single-character base case.
2. For each index i, call the helper twice: once with (i, i) for odd-length palindromes and once with (i, i+1) for even-length ones.
3. In the helper, advance left left and right right while both pointers are in bounds and the characters match.
4. After the loop exits, left and right are both one step past the palindrome boundary — the actual palindrome is s[left+1 : right], with length right - left - 1.
5. Update best_start and best_length if this palindrome is strictly longer than the current best.
6. Return s[best_start : best_start + best_length].

1def longestPalindrome(s: str) -> str:
2    best_start, best_length = 0, 1
3
4    def expand(left: int, right: int) -> None:
5        nonlocal best_start, best_length
6        while left >= 0 and right < len(s) and s[left] == s[right]:
7            left -= 1
8            right += 1
9        # After the loop, s[left] != s[right] or out of bounds;
10        # the palindrome spans [left+1, right-1], length = right - left - 1
11        length = right - left - 1
12        if length > best_length:
13            best_length = length
14            best_start = left + 1
15
16    for i in range(len(s)):
17        expand(i, i)      # odd-length: single character center
18        expand(i, i + 1)  # even-length: gap between characters
19
20    return s[best_start : best_start + best_length]

Time: O(n²) — there are 2n−1 centers, and each expansion visits at most O(n) characters in the worst case. Space: O(1) — only a constant number of integer variables; the result is a view into the original string, not a copy until returned.

Complexity Summary

Common Mistakes

• Skipping the even-length case: Only calling expand(i, i) misses palindromes like "abba" — even-length palindromes have no single center character. You must also call expand(i, i+1) for every index.
• Off-by-one when reading the palindrome boundary: After the loop, left and right have both gone one step past the edges of the palindrome. The palindrome is s[left+1 : right], not s[left : right+1]. Getting this backwards gives a two-character-too-wide string.
• Wrong length formula: The palindrome length is right - left - 1, not right - left + 1. Since left is one before the start and right is one after the end, the span is (right - 1) - (left + 1) + 1 = right - left - 1.
• Using >= instead of > when updating the best: Using >= causes the answer to shift to the last tied palindrome found rather than the first. The problem accepts any valid answer, but being consistent about strict > avoids subtle bugs in problems where the position matters.
• Not initializing for the single-character base case: If the input has no palindrome longer than one character (e.g., "abcd"), the expansion loops all exit immediately. Initializing best_length = 1 and best_start = 0 returns s[0] correctly without any special-case code.

Related Problems

• palindromic-substrings — count every palindromic substring using the same expand-around-center technique, just incrementing a counter instead of tracking the longest
• longest-palindromic-subsequence — characters no longer need to be contiguous; the palindrome can skip positions, which forces a DP approach instead
• palindrome-partitioning — split a string into all-palindrome parts; palindrome detection via expansion is a natural subproblem
• valid-palindrome — the fundamental two-pointer palindrome check that underlies the expansion step here
• palindrome-linked-list — palindrome verification on a linked list using the two-pointer meeting-in-the-middle technique