Longest Palindromic Substring

The difficult part is not recognizing a palindrome. It is preserving contiguity while avoiding repeated work.

A strong Longest Palindromic Substring solution treats every possible symmetry center as a starting point. Expand outward while the boundary characters match, then keep the best range found. Because palindromes can have one-character centers or gap centers, both cases must be checked.

Read the exact contract

Given a non-empty string s containing digits and English letters, return one longest contiguous substring that reads identically from left to right and right to left.

Two details control the algorithm:

1. The answer must be a substring, so its characters occupy one uninterrupted range of s.
2. If several answers have the same maximum length, any one is valid.

For example:

s = "babad"

Both "bab" and "aba" are valid answers.

s = "cbbd"

The answer is "bb".

That second example exposes a common failure. "bb" has even length, so its center is the gap between the two b characters. An algorithm that checks only character centers cannot find it.

A substring cannot skip characters. In "cbbd", "bd" is a subsequence, but not a substring because the characters are not adjacent. Longest palindromic subsequence is a different problem with a different state model.

The structural clues here are:

• We need a best contiguous range.
• The range is defined by bilateral symmetry.

Once those clues are visible, the center of the palindrome becomes the natural place to scan.

See the center-expansion pattern

Every palindrome has one of two center types:

• An odd-length palindrome has one character at its center.
• An even-length palindrome has a gap between two adjacent characters at its center.

For example:

"aba"   center: the character "b"
"abba"  center: the gap between the two "b" characters

For a chosen center, compare the characters immediately to its left and right. If they match, expand one step farther in both directions. Stop when a boundary leaves the string or the next pair differs.

For "babad":

• The character at index 1 is the center of "bab".
• The character at index 2 is the center of "aba".

Both candidates have length 3, so either can remain as the answer.

For "cbbd", the gap between indices 1 and 2 is an even center:

c [b b] d

Expanding from that gap produces "bb".

There are n character centers and n - 1 gaps between characters. A loop over every index can handle both:

expand(i, i)       # odd-length center
expand(i, i + 1)   # even-length center

This is state tracking at two levels:

• The expansion tracks one locally valid palindromic range.
• The outer loop tracks the best range found globally.

The local range moves. The global answer only improves.

Use brute force as the baseline

The direct approach is:

1. Enumerate every contiguous substring.
2. Check whether each candidate is a palindrome.
3. Keep the longest one.

A string of length n has O(n²) contiguous substrings. If checking each candidate scans its characters, the total work can reach O(n³).

Brute force is still valuable as a baseline because it shows what the optimized method removes: repeated checks of ranges that share the same center and inner symmetry.

Approach	Time	Auxiliary space	Main tradeoff
Enumerate and check every substring	O(n³) straightforwardly	Usually O(1) beyond candidates	Simple, but repeats boundary comparisons
Dynamic programming	O(n²)	O(n²)	Stores whether each range is palindromic
Center expansion	O(n²)	O(1)	Direct symmetry reasoning with little state

Dynamic programming can determine whether s[i:j+1] is a palindrome from its matching endpoints and inner range. That works, but it stores a table for all ranges.

Center expansion uses the symmetry already present in the answer. With the stated maximum length of 1000, I would start there in an interview: the quadratic bound is sufficient, the state is visible, and the proof is short.

Define the state and endpoint contract

The helper receives two indices, left and right, representing a possible center:

• left == right: odd-length center
• right == left + 1: even-length center

It expands while the indices are valid and the boundary characters match:

while (
    left >= 0
    and right < n
    and s[left] == s[right]
):
    left -= 1
    right += 1

The loop moves one step beyond the final valid palindrome. To make empty even candidates safe, use a half-open range for the helper's return value:

(start, end)

Here, start is inclusive and end is exclusive. After the loop:

start = left + 1
end   = right

The candidate is s[start:end], and its length is:

end - start

This contract handles every case consistently:

• Odd center "a" returns a range such as (2, 3).
• Even center "bb" returns (1, 3).
• An immediately failing gap, such as (0, 1) in "abc", returns (1, 1), an empty range.
• A gap at the final index also returns an empty range.

That last point matters. An even center does not begin with a palindrome automatically. It begins with a gap. If the adjacent characters differ, its maximal palindrome is empty.

Track the global answer using:

best_start
best_length

Store indices rather than slicing during expansion. Slice only once at the end.

Update only when the candidate is strictly longer:

if candidate_length > best_length:
    ...

That preserves the first maximum found. Since tied answers are valid, replacing an equal-length answer provides no benefit.

State the invariant precisely

The invariant differs slightly by center type.

For an odd center, before each successful comparison, the current inclusive range from left through right is a palindrome. It begins as one character, which is trivially palindromic.

For an even center, the initial state represents a gap between left - 1 and right, rather than a non-empty palindrome. If the first pair matches, the range s[left:right + 1] becomes a palindrome. If it does not, the maximal candidate is empty.

After every successful comparison, the expanded inclusive range is a palindrome because:

1. The inner range was already palindromic.
2. The newly added left and right characters are equal.

When the loop stops, the last successful range remains valid. The failed comparison lies outside it, so it cannot be extended into a larger palindrome centered at the same position.

The helper's half-open return value records exactly that last valid range:

return left + 1, right

The local state has a clear obligation: return the maximal palindromic range for one center, including the possibility of an empty range for a failed even center.

The global state has a different obligation: remember the longest candidate returned by any center.

Prove that every answer is covered

The correctness argument follows the structure of the algorithm.

Every palindrome has a scanned center

An odd-length palindrome has one middle character. An even-length palindrome has one gap between its two middle characters.

The algorithm checks every character center and every adjacent-character gap. Therefore, every possible palindromic substring has a center that the algorithm examines.

Expansion preserves symmetry

Suppose the current range is a palindrome. If the next characters on the left and right are equal, adding both preserves bilateral symmetry.

For example:

"aba" -> "cabac"

The inner range "aba" is palindromic, and the new outer characters are both "c". The expanded range is also palindromic.

Each center reaches its maximum

Expansion stops only when the next comparison would leave the string or the two next boundary characters differ.

If the first comparison for an even center fails, the maximal palindrome for that gap is empty. If the gap is at the string boundary, it is also empty. Neither case can beat the length-one fallback already stored in the global state.

Otherwise, every successful comparison grows the palindrome by two characters. When expansion stops, no larger palindrome with that center exists. The helper therefore returns the maximal candidate for that center.

The global state selects a longest candidate

Every palindromic substring belongs to one of the scanned centers. The expansion for that center reaches at least as far as the substring, and the outer loop compares all returned lengths.

Therefore, best_start and best_length describe one longest palindromic substring.

Dry-run the important cases

Odd-length tie: "babad"

At index 1, use the odd center (1, 1):

• Compare s[1] with s[1]: match.
• Expand to (0, 2).
• Compare "b" with "b": match.
• Expand beyond the string.
• Return the half-open range (0, 3), which is "bab".

Later, index 2 produces "aba" with the same length. The strict-greater update leaves "bab" unchanged. That is valid because tied answers are allowed.

Even-length answer: "cbbd"

At i = 1, use the even center (1, 2):

• Compare "b" with "b": match.
• Expand to (0, 3).
• Compare "c" with "d": mismatch.
• Return (1, 3), which is "bb".

An odd-only implementation never examines the gap between the two b characters.

Immediately failing even center: "abc"

At i = 0, the even helper starts with (0, 1):

• Compare "a" with "b": mismatch.
• Return (1, 1).
• The candidate length is 1 - 1 = 0.

No invalid inclusive range is created, and the empty candidate cannot replace the length-one fallback.

Single character: "a"

The odd center returns (0, 1), so the best candidate has length 1. The even center returns an empty range. The function returns "a".

No repeated characters: "abc"

No expansion grows beyond a single character. Because updates require a strictly larger candidate, the first character remains the answer: "a".

Implement the Python solution

def longest_palindrome(s: str) -> str:
    n = len(s)

    # The input is non-empty, so one character is always a valid fallback.
    best_start = 0
    best_length = 1

    def expand(left: int, right: int) -> tuple[int, int]:
        while (
            left >= 0
            and right < n
            and s[left] == s[right]
        ):
            left -= 1
            right += 1

        # Return a half-open range: [start, end).
        return left + 1, right

    for i in range(n):
        # Odd-length palindrome centered on s[i].
        start, end = expand(i, i)
        length = end - start

        if length > best_length:
            best_start = start
            best_length = length

        # Even-length palindrome centered between s[i] and s[i + 1].
        start, end = expand(i, i + 1)
        length = end - start

        if length > best_length:
            best_start = start
            best_length = length

    return s[best_start:best_start + best_length]

The variables have separate, visible jobs:

• left and right track local symmetry during one expansion.
• start and end describe that center's maximal half-open range.
• best_start and best_length track the global answer.
• The final slice uses Python's exclusive upper-bound convention.

Representative results:

print(longest_palindrome("babad"))  # "bab" or "aba"
print(longest_palindrome("cbbd"))   # "bb"
print(longest_palindrome("a"))      # "a"
print(longest_palindrome("abc"))    # "a"

For "babad", the exact output depends on which tied length-three palindrome is found first. Both outputs satisfy the contract.

Complexity and boundary checks

There are O(n) centers. Each expansion can inspect O(n) characters in the worst case, especially for strings containing many repeated characters.

Therefore:

• Time: O(n²)
• Auxiliary space: O(1) before the returned substring

The implementation stores indices and counters rather than a table of all ranges. The returned string itself may require output storage when sliced; that is separate from the algorithm's auxiliary state.

Before submitting, test:

• A length-one string: "a"
• All identical characters: "aaaa"
• No repeated characters: "abc"
• A full-string palindrome: "racecar"
• An even-length winner: "cbbd"
• An odd-length winner: "babad"
• Multiple tied maximum answers
• A palindrome beginning or ending at a string boundary
• An immediately failing even center

Manacher's algorithm can reduce the time bound to linear, but it adds bookkeeping around transformed strings and palindrome radii. With n <= 1000, center expansion is usually the better interview choice: the quadratic bound is sufficient, and the reasoning is easier to inspect under pressure.

The transferable recognition rule

When a problem asks for the best contiguous range defined by bilateral symmetry:

1. Enumerate the possible centers.
2. Expand while the local symmetry condition holds.
3. Represent empty candidates safely.
4. Track only the best global range.

Before submitting, verify that you tested both a character center and a gap center. Then inspect the endpoint convention: inclusive ranges and half-open ranges are both valid, but mixing them is where correct reasoning turns into an off-by-one bug.

Clear the range. Preserve the invariant. Keep the best state. That is the pattern.