What Is a Palindrome? The Interview Question Every Engineer Should Know

A palindrome reads the same forward and backward. "racecar" is a palindrome. "hello" is not. You learned this in fifth grade and then promptly forgot about it until an interviewer asked you to find the longest one in a string and suddenly it's 2D DP territory.

The palindrome interview question appears across easy, medium, and occasionally hard LeetCode problems. They test two-pointer thinking, expand-from-center pattern recognition, and 2D DP reasoning. Here's the full range, so you're not caught thinking "how hard can it be?" when it absolutely can be.

Know Which Form the Problem Gives You

A string palindrome is one whose characters, reversed, produce the same string. "madam", "level", "noon". Any single character qualifies. So does the empty string, by convention. Case matters unless the problem says otherwise: "Racecar" fails strict comparison, but LeetCode 125 tells you to ignore case and strip non-alphanumeric characters first.

Number palindromes work the same way on the decimal representation. 121 is a palindrome. 123 is not. The classic trap: negative numbers. Is -121 a palindrome? No, because "-121" reversed is "121-". Most numeric palindrome problems want you to avoid string conversion, which makes the integer math the interesting part.

How to Check a String

Two Pointers

This is the approach to reach for first. Place a pointer at each end and walk them inward, comparing characters as you go.

def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

Time: O(n). Space: O(1). You check at most n/2 pairs and allocate nothing extra.

The key insight: once left >= right, every symmetric pair has been verified. You never need to look at more than half the string. Five lines, done, and you look like someone who knows what they're doing.

Reverse and Compare

def is_palindrome(s: str) -> bool:
    return s == s[::-1]

One line. Correct. Elegant, even. But s[::-1] allocates a new string, making this O(n) space. In Python this is often fine, but if the interviewer asks you to optimize for space, two pointers is the answer they want. Knowing why you'd switch matters more than the one-liner.

Integers Without String Conversion

LeetCode 9. The standard approach reverses only the second half of the number and compares it to the first half.

def is_palindrome(x: int) -> bool:
    if x < 0:
        return False
    if x != 0 and x % 10 == 0:
        return False

    reversed_half = 0
    while x > reversed_half:
        reversed_half = reversed_half * 10 + x % 10
        x //= 10

    return x == reversed_half or x == reversed_half // 10

The loop runs until reversed_half >= x, meaning you've processed half the digits. For odd-length numbers, the middle digit lands in reversed_half, so the second comparison divides it away. The two early exits handle negatives and trailing zeros (no palindrome with more than one digit ends in 0).

Time: O(log n). Space: O(1). This is the version interviewers remember.

Where It Gets Harder: Substrings

Longest Palindromic Substring

LeetCode 5. Find the longest contiguous palindromic substring. This is where "oh, palindromes, I know this" meets "wait, what do you mean expand from center."

The expand-from-center approach runs in O(n²) time and O(1) space. For each position, expand outward while characters match. You need two expansions per position: one for odd-length palindromes (centered on a character) and one for even-length (centered between two characters).

def longest_palindrome(s: str) -> str:
    def expand(left: int, right: int) -> str:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]

    result = ""
    for i in range(len(s)):
        odd = expand(i, i)
        even = expand(i, i + 1)
        if len(odd) > len(result):
            result = odd
        if len(even) > len(result):
            result = even
    return result

You can also solve this with DP using a 2D boolean table where dp[i][j] is true when s[i:j+1] is a palindrome. Expand-from-center is usually better in interviews because it uses O(1) space instead of O(n²), and it doesn't require you to explain a diagonal table traversal while the interviewer watches you break a sweat.

Manacher's algorithm solves the same problem in O(n) time. The implementation is enough to trip most candidates. Don't volunteer it unless the interviewer asks about linear time. Knowing it exists and roughly why it's faster is usually enough to score points without opening that particular can of worms.

Counting Palindromic Substrings

LeetCode 647. Same expand-from-center idea. Instead of tracking the longest, count every expansion that succeeds.

def count_substrings(s: str) -> int:
    count = 0
    for i in range(len(s)):
        left, right = i, i
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
        left, right = i, i + 1
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
    return count

Same pattern, different punchline. If you've internalized expand-from-center, this one is nearly free.

Subsequences Are a Separate Problem

LeetCode 516. Longest Palindromic Subsequence. A subsequence does not have to be contiguous: "bbbab" has "bbbb" as its longest palindromic subsequence (length 4) because you can skip the 'a'.

Don't confuse this with the substring problem. Substring = contiguous. Subsequence = can skip characters. Interviewers use these interchangeably in conversation, which causes candidates to code the wrong problem entirely, finish with five minutes left, and wonder why the interviewer looks confused. Clarify upfront.

This is a 2D DP problem. dp[i][j] is the length of the longest palindromic subsequence in s[i:j+1].

def longest_palindrome_subseq(s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]

    for i in range(n):
        dp[i][i] = 1

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

    return dp[0][n - 1]

Time: O(n²). Space: O(n²), reducible to O(n) with a rolling array. The dynamic programming framework covers that reduction in detail.

Palindromes in Disguise

The pattern hides in several other interview problems, usually right after you thought you were done with palindromes forever.

Palindrome Linked List (LeetCode 234): find the middle of the list, reverse the second half, compare the two halves. The palindrome check itself is the easy part. The fast/slow pointer work is where candidates lose time.

Minimum insertions to make a string a palindrome (LeetCode 1312): the answer is n - longest_palindromic_subsequence(s). Once you see that connection, the DP from 516 does the rest. Before you see it, you're staring at the problem for eight minutes wondering what insertions have to do with subsequences.

Valid Palindrome II (LeetCode 680): can you delete at most one character? When the two-pointer comparison fails, try skipping either the left or right character and check if the remaining substring is a palindrome. Two recursive checks, both O(n), easy to verify, satisfying to explain.

The Edge Cases That Bite

These separate candidates who thought it through from candidates who coded the happy path and declared victory.

Empty string. Is "" a palindrome? Yes, by convention. Clarify before writing a line.
Single character. Always a palindrome. Verify your two-pointer loop handles left == right.
All same characters. "aaaa" always qualifies. Worth a quick sanity check.
Spaces and punctuation. LeetCode 125 strips non-alphanumeric characters. Know whether your problem does.
Case sensitivity. "Racecar" vs "racecar". Ask before coding.
Negative integers. Always return false. The minus sign breaks the symmetry.
Trailing zeros in integers. 10 reversed is 01 = 1, so 10 is not a palindrome. The x % 10 == 0 and x != 0 guard handles this before the main loop.

State at least two of these out loud before you declare your solution done. Interviewers score the verification step separately from the algorithm. Solving the happy path and going silent is how correct code still gets "no hire."

Complexity Reference

Problem	Approach	Time	Space
Palindrome check (string)	Two pointers	O(n)	O(1)
Palindrome check (string)	Reverse compare	O(n)	O(n)
Palindrome check (integer)	Half-reverse	O(log n)	O(1)
Longest palindromic substring	Expand from center	O(n²)	O(1)
Longest palindromic substring	DP table	O(n²)	O(n²)
Longest palindromic substring	Manacher's	O(n)	O(n)
Count palindromic substrings	Expand from center	O(n²)	O(1)
Longest palindromic subsequence	DP	O(n²)	O(n²)

Why the Palindrome Interview Question Layers So Well

Palindromes are layered by design. A basic check is five lines. Ask for O(1) space and you teach two pointers. Ask for all palindromic substrings and you teach expand-from-center. Ask for the longest palindromic subsequence and you're in 2D DP territory. The same concept scales from easy to hard without requiring exotic data structures, which is exactly what makes it a favorite interview topic.

The insight that connects all of it: a palindrome mirrors itself around a center, and every efficient solution exploits that mirror. For the substring problems, the follow-up is almost always "can you do it in linear time?" Knowing that Manacher's exists, and having a rough sense of how it avoids redundant work, is the kind of depth that earns a strong hire signal on algorithms. You don't need to implement it from memory. You need to know why the naive approach does redundant work and what property the algorithm exploits to skip it.

If you want to practice explaining these approaches out loud under timed conditions, SpaceComplexity runs voice-based DSA mock interviews with rubric-based feedback. The edge case discussion and complexity analysis are scored separately from whether your code compiles.