Palindromes are a favourite interview topic because the same word covers three genuinely different difficulty tiers:

1. Verify one string is a palindrome — two pointers, $O(n)$, Easy.
2. Find palindromic substrings inside a string — expand around centre, $O(n^2)$, Medium.
3. Build a palindrome by deleting or inserting — interval DP, $O(n^2)$, Medium to Hard.

The mistake that costs the most time is reaching for tier 3 machinery on a tier 2 problem. This page separates them, and gives you the cue for each.

What you’ll learn

• The two-pointer verification template, and the “at most one deletion” variant.
• Expand around centre: why there are 2n - 12n - 1 centres, not nn.
• Why “substring” means expand-around-centre and “subsequence” means DP — the single most useful distinction on this page.
• Three real LeetCode problems solved in the browser: 5, 647, 680.

The cue

Tier 1 — verify with two pointers

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True
 
 
print(is_palindrome("racecar"))   # True
print(is_palindrome("abca"))      # False

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True
 
 
print(is_palindrome("racecar"))   # True
print(is_palindrome("abca"))      # False

$O(n)$ time, $O(1)$ space. s == s[::-1]s == s[::-1] is also $O(n)$ but allocates a reversed copy, so it is $O(n)$ space — fine to mention, and fine to use unless asked for constant space.

For LC 125 the only additions are skipping non-alphanumeric characters and lower-casing:

def is_palindrome_alnum(s):
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():    # skip junk
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True
 
 
print(is_palindrome_alnum("A man, a plan, a canal: Panama"))   # True

def is_palindrome_alnum(s):
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():    # skip junk
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True
 
 
print(is_palindrome_alnum("A man, a plan, a canal: Panama"))   # True

Tier 2 — expand around centre

Every palindrome has a centre. Grow outward from each possible centre while the characters match; each expansion step is $O(1)$ and finds a new palindrome.

The detail that catches people: a palindrome of even length has its centre between two characters. So there are 2n - 12n - 1 centres — nn single-character centres and n - 1n - 1 gaps.

def longest_palindrome(s):
    if not s:
        return ""
    best_left, best_len = 0, 1
 
    def expand(left, right):
        nonlocal best_left, best_len
        while left >= 0 and right < len(s) and s[left] == s[right]:
            if right - left + 1 > best_len:
                best_left, best_len = left, right - left + 1
            left -= 1
            right += 1
 
    for i in range(len(s)):
        expand(i, i)          # odd-length centre: a single character
        expand(i, i + 1)      # even-length centre: the gap after i
 
    return s[best_left:best_left + best_len]
 
 
print(longest_palindrome("babad"))   # "bab"  ("aba" is equally correct)
print(longest_palindrome("cbbd"))    # "bb"

def longest_palindrome(s):
    if not s:
        return ""
    best_left, best_len = 0, 1
 
    def expand(left, right):
        nonlocal best_left, best_len
        while left >= 0 and right < len(s) and s[left] == s[right]:
            if right - left + 1 > best_len:
                best_left, best_len = left, right - left + 1
            left -= 1
            right += 1
 
    for i in range(len(s)):
        expand(i, i)          # odd-length centre: a single character
        expand(i, i + 1)      # even-length centre: the gap after i
 
    return s[best_left:best_left + best_len]
 
 
print(longest_palindrome("babad"))   # "bab"  ("aba" is equally correct)
print(longest_palindrome("cbbd"))    # "bb"

Expand-around-centre is the interview answer: same time as the DP with $O(1)$ space, and far less code. Manacher’s is the theoretically optimal $O(n)$ solution — know that it exists and is the answer to “can you do better than $O(n^2)$”, but nobody sane expects you to derive it live.

Tier 3 — when it becomes DP

Once you may skip characters (subsequence) or modify the string (insert/delete), centres stop helping and you need interval DP over (i, j)(i, j) ranges.

The one identity worth memorising:

$\text{min insertions to make } s \text{ a palindrome} = n - \text{LPS}(s)$

where $\text{LPS}$ is the longest palindromic subsequence — and $\text{LPS}(s) = \text{LCS}(s, \text{reverse}(s))$. So LC 1312 reduces to a longest-common-subsequence you already know how to write. These live in Classic DP and DP on Grids and Intervals.

Practice — real LeetCode problems

LC 5 — Longest Palindromic Substring · Medium

Problem. Given a string ss, return the longest palindromic substring in ss.

Constraints. 1 <= len(s) <= 10001 <= len(s) <= 1000, digits and English letters.

Examples. "babad""babad" gives "bab""bab" — "aba""aba" is also accepted · "cbbd""cbbd" gives "bb""bb"

LC 647 — Palindromic Substrings · Medium

Problem. Given a string ss, return the number of palindromic substrings in it. Substrings at different positions count separately even if they are identical.

Constraints. 1 <= len(s) <= 10001 <= len(s) <= 1000, lowercase English letters.

Examples. "abc""abc" gives 33 ("a""a", "b""b", "c""c") · "aaa""aaa" gives 66 ("a""a"×3, "aa""aa"×2, "aaa""aaa")

LC 680 — Valid Palindrome II · Easy

Problem. Given a string ss, return TrueTrue if it can be made a palindrome by deleting at most one character.

Constraints. 1 <= len(s) <= 10^51 <= len(s) <= 10^5, lowercase English letters.

Examples. "aba""aba" gives TrueTrue (already one) · "abca""abca" gives TrueTrue (delete "c""c" or "b""b") · "abc""abc" gives FalseFalse

LeetCode problem set

Interview follow-ups

Edge-case checklist

• Single character — always a palindrome; the answer to LC 5 has length 11, and LC 647 counts 11.
• Two characters — "ac""ac" gives "a""a" (or "c""c"); "bb""bb" gives "bb""bb". The fastest check that you handled even centres.
• All identical — "aaaa""aaaa"; the worst case for expansion, and where slicing inside the loop turns $O(n^2)$ into $O(n^3)$.
• No palindrome longer than 1 — "abc""abc"; make sure best_lenbest_len starts at 11, not 00.
• Ties for longest — multiple valid answers; do not assume one exact string.
• All non-alphanumeric (LC 125) — ".,"".," must return TrueTrue and must not run off the end of the string.
• Mismatch needing the right-side deletion (LC 680) — "cbbcc""cbbcc"; catches one-sided solutions.
• Empty string — vacuously a palindrome, though most of these problems guarantee at least one character.

Recap

• Three tiers, three techniques. Verify with two pointers ($O(n)$), find substrings by expanding around centres ($O(n^2)$, $O(1)$ space), build/modify with interval DP.
• Substring vs. subsequence is the distinction that decides which tier you are in. Read the problem statement twice.
• There are 2n - 12n - 1 centres — always expand both (i, i)(i, i) and (i, i + 1)(i, i + 1).
• Track indices, not strings, inside expansion loops; slicing per improvement can add a factor of nn.
• “At most one deletion” is one branch, not a counter — and you must try both sides.
• min insertions = n - LPS(s)min insertions = n - LPS(s), and LPS(s) = LCS(s, reverse(s))LPS(s) = LCS(s, reverse(s)) — one identity that collapses several Hard problems into a known DP.
• Manacher’s gives $O(n)$; know it exists, and that expand-around-centre is what you are expected to write.

Next: Trie Patterns — the prefix tree, and the problems that are unreasonably easy once you have one.