Palindrome Verification

A palindrome reads the same forwards and backwards. It sounds like a trivial property, but checking for it shows up constantly: as a standalone problem, as a subroutine inside harder algorithms, and in several clever variations that test whether you truly understand the two-pointer technique. Let's start with the most common version and build from there.

Valid Palindrome

LeetCode 125 asks: given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring case. So "A man, a plan, a canal: Panama" is a palindrome, but "race a car" is not.

The approach is straightforward. Place one pointer at the beginning of the string and another at the end. Move them toward each other. At each step, skip any character that is not alphanumeric: spaces, punctuation, colons, all ignored. Then compare the characters at both pointers, case-insensitively. If they ever disagree, the string is not a palindrome. If the pointers meet or cross without a mismatch, it is.

Walking through "A man, a plan, a canal: Panama"

Let us trace the algorithm on this classic example. We never build a cleaned copy of the string. The pointers simply skip over irrelevant characters in place.

left starts at index 0 ('A'), right at index 29 ('a'). Both are alphanumeric. Lowercase comparison: 'a' == 'a'. Match. Move inward.

left moves to index 1, which is a space, so skip it. Index 2 is 'm'. right moves to index 28, which is 'm'. Compare: match. Move inward.

left advances past another space to index 3 ('a'). right retreats to index 27 ('a'). Match again. This process continues: left skips commas and spaces as it advances, right skips the colon and spaces as it retreats. Every time both pointers land on alphanumeric characters, the lowercase forms match.

Eventually the pointers meet in the middle. Every pair matched, so the answer is true.

The key observation is that the two pointers never backtrack. Each character in the string is visited at most once by either left or right, giving us $O(n)$ time with $O(1)$ space.

def isPalindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            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

You will sometimes see solutions that first build a cleaned string with ''.join(c.lower() for c in s if c.isalnum()) and then compare it to its reverse. That works and is arguably cleaner to read, but it uses $O(n)$ extra space. In an interview, mentioning both approaches and their tradeoffs is a good move.

Valid Palindrome II

LeetCode 680 raises the stakes: given a string of lowercase letters, determine if it can become a palindrome by deleting at most one character. The string "abca" returns true because deleting either the 'b' or the 'c' produces "aca" or "aba", both palindromes.

The naive approach would try deleting every character and checking if the result is a palindrome, which is $O(n^2)$. The insight that makes this $O(n)$ is simple: start with the same two-pointer scan. As long as the characters at left and right match, move inward. When you hit the first mismatch, you have two choices: delete the character at left (check whether s[left+1..right] is a palindrome) or delete the character at right (check whether s[left..right-1] is a palindrome). If either remaining substring is a palindrome, the answer is true.

Why does this work? Before the mismatch, every pair of characters matched perfectly, so no deletion was needed in that outer region. The mismatch is the first place where a deletion might help. At that point there are exactly two candidates for which character to remove, and you only need to verify these two possibilities. After the deletion, no further deletions are allowed, so the helper function is a strict palindrome check.

Walking through "abca"

Start with left = 0 ('a'), right = 3 ('a'). They match. Move inward.

Now left = 1 ('b'), right = 2 ('c'). Mismatch. We branch:

• Skip left (delete the 'b'): check if s[2..2] = "c" is a palindrome. A single character is always a palindrome. This branch succeeds.
• Skip right (delete the 'c'): check if s[1..1] = "b" is a palindrome. Also succeeds.

Either branch works, so we return true. In practice, the code tries both with an or and short-circuits on the first success.

Consider a trickier example: "abcda". We match 'a' with 'a' on the outside, then hit left = 1 ('b') versus right = 3 ('d'). Skip left: is "cd" a palindrome? No. Skip right: is "bc" a palindrome? No. Return false, since this string cannot be fixed with a single deletion.

def validPalindrome(s):
    def is_palindrome(lo, hi):
        while lo < hi:
            if s[lo] != s[hi]:
                return False
            lo += 1
            hi -= 1
        return True

    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return is_palindrome(left + 1, right) or is_palindrome(left, right - 1)
        left += 1
        right -= 1
    return True

The outer loop and the inner is_palindrome call together examine at most n characters total, so the time complexity is $O(n)$. Space is $O(1)$.

Palindrome checking as a building block

The simple palindrome check appears as a subroutine in many harder problems, and it is worth recognizing when that is happening.

In Palindrome Partitioning (LeetCode 131), you split a string into substrings where every piece is a palindrome. The backtracking algorithm tries every possible first cut, and for each candidate substring it calls a palindrome check before recursing on the remainder. The palindrome verification is the inner loop that gets called many times.

In Longest Palindromic Substring (LeetCode 5), the expand-around-center approach is essentially running palindrome verification outward from each possible center. You pick a center, then extend left and right as long as the characters match. It is the same comparison logic, just expanding instead of converging.

In Palindromic Substrings (LeetCode 647), you count the total number of palindromic substrings. Again, expand-around-center or a DP table where each cell answers "is s[i..j] a palindrome?", both built on the same fundamental check.

Because palindrome verification appears so frequently inside other algorithms, it is worth having the two-pointer version deeply internalized. The in-place $O(1)$-space version avoids creating new strings on every call, which matters when the check runs inside a loop or recursion tree that may invoke it $O(n^2)$ times.

Checking vs. finding: different problems, different techniques

There is an important conceptual distinction between the problems in this article and problems like Longest Palindromic Substring (LeetCode 5). Here, we are given a specific string (or substring) and asking a yes/no question: is it a palindrome? The answer is a simple two-pointer scan from both ends, $O(n)$ time.

Finding palindromic substrings is a fundamentally different challenge. You are searching over all possible substrings, which naively takes $O(n^2)$ candidates, each requiring $O(n)$ to check, for $O(n^3)$ total. The expand-around-center technique improves this to $O(n^2)$ by starting at each possible center and expanding outward as long as characters match. Manacher's algorithm pushes it further to $O(n)$ by cleverly reusing previously computed information. These are different algorithms from the simple verification technique discussed here.

The palindrome verification approach, two pointers converging inward, is the right tool when you already know which substring you want to check. It is the inner loop, not the outer search. Knowing when you need verification versus when you need search is the key to picking the right approach.

Complexity analysis

Valid Palindrome runs in $O(n)$ time where n is the length of the string. Each character is visited at most once by either the left or right pointer. Space is $O(1)$ if you skip non-alphanumeric characters in place rather than building a cleaned copy.

Valid Palindrome II is also $O(n)$. In the worst case, the outer loop scans most of the string before hitting a mismatch, and then the helper scans the remaining substring. The total work across the outer loop and the one helper call is at most 2n character comparisons. Space is $O(1)$, since the helper uses its own pair of index variables on the stack, nothing more.

Recognizing this pattern

You're probably looking at palindrome verification when:

• The problem asks whether a string (or a cleaned version of it) reads the same forwards and backwards.
• You need $O(1)$ extra space, with no reversing into a new buffer.
• You're allowed a small number of "skips" or "deletions" while still calling the result a palindrome.
• The check is a building block inside a larger algorithm (partitioning, dynamic programming, or a streaming queue).

Common templates:

• Two-pointer scan from the ends: converge while comparing characters; skip non-relevant ones in place. Example: Valid Palindrome.
• One-skip palindrome: on first mismatch, try skipping left or right and re-verify the substring. Example: Valid Palindrome II.
• K-skip palindrome (DP): when more than one skip is allowed, fall back to longest-palindromic-subsequence DP. Example: Valid Palindrome IV.
• Linked-list palindrome: find the middle with fast/slow, reverse the second half, compare. Example: Palindrome Linked List.
• Number-as-palindrome: reverse half the digits and compare, avoiding string conversion. Example: Palindrome Number.