technical interviews

Valid Palindrome

Check if a string is a palindrome (ignoring non-alphanumeric characters)

Problem

Given a string s, determine if it is a palindrome, considering only alphanumeric characters (a-z, A-Z, 0-9) and ignoring spaces, punctuation, and case.

Difficultyintroductory

R — READ

R

READ

Question

What counts as a valid character? Is 'A man, a plan, a canal: Panama' valid?

Focus

Only alphanumeric characters matter. Ignore spaces and punctuation. Case-insensitive.

What the Interviewer is Evaluating

Do you understand what we're actually comparing? Do you ask clarifying questions?

Common Mistake

Treating every character as part of the palindrome check.

Input:  s = "A man, a plan, a canal: Panama"
After cleaning: "amanaplanacanalpanama"
Is it a palindrome? Yes, it reads the same forwards and backwards.

O — OBSERVE

O

OBSERVE

Question

What's the structure of a palindrome?

Focus

First half mirrors the second half. We can use two pointers from both ends and move toward the middle.

What the Interviewer is Evaluating

Can you recognize that two-pointers suits this problem?

Common Mistake

Building a reversed string or using recursion when two pointers is simpler.

Example: "a man a"
Clean: "amanaa"
• Left pointer at 'a', right at 'a'. Match ✓
• Left moves to 'm', right moves to 'a'. Match ✓
• Left moves to 'a', right moves to 'n'. Match ✓
• Pointers meet or cross. It's a palindrome.

P — PSEUDOCODE

P

PSEUDOCODE

Question

How do I check with two pointers?

Focus

Clean the string (keep alphanumerics, lowercase). Use left and right pointers. Compare and move inward.

What the Interviewer is Evaluating

Clear step-by-step logic.

Common Mistake

Pseudocode that doesn't explain the cleaning or pointer movement clearly.

1. Convert string to lowercase and remove non-alphanumeric
2. Initialize left = 0, right = len(cleaned) - 1
3. While left < right:
   a. If cleaned[left] != cleaned[right], return false
   b. Move left forward, right backward
4. If loop completes without mismatch, return true

I — IMPLEMENT

I

IMPLEMENT

Question

How do I write clean, readable code?

Focus

Use Python's isalnum() for character checking. Clean and compare with two pointers.

What the Interviewer is Evaluating

Code clarity and correctness.

Common Mistake

Complex regex or unclear variable names.

def isPalindrome(s):
    """
    Check if a string is a palindrome (alphanumeric only, case-insensitive).
    
    Args:
        s: The input string
    
    Returns:
        True if palindrome, False otherwise
    """
    # Clean: keep only alphanumeric, convert to lowercase
    cleaned = ''.join(c.lower() for c in s if c.isalnum())
    
    # Two pointers
    left, right = 0, len(cleaned) - 1
    while left < right:
        if cleaned[left] != cleaned[right]:
            return False
        left += 1
        right -= 1
    
    return True

T — TEST

T

TEST

Question

Does my code work on all test cases?

Focus

Test: spaces/punctuation, case differences, non-palindromes, edge cases.

What the Interviewer is Evaluating

Thoroughness. Did you test edge cases?

Common Mistake

Only testing simple strings.

Test 1: "A man, a plan, a canal: Panama" → True ✓
Test 2: "0P" → False ✓
Test 3: "a." → True ✓
Test 4: "" → True (empty is palindrome) ✓
Test 5: "12321" → True ✓
Test 6: "race a car" → False ✓

A — ANALYZE

A

ANALYZE

Question

What's the complexity?

Focus

Two passes: cleaning takes O(n), two-pointer comparison takes O(n).

What the Interviewer is Evaluating

Clear complexity analysis.

Common Mistake

Ignoring the cost of string cleaning.

TIME O(n)
SPACE O(n)

Why: Cleaning the string (filtering alphanumeric and lowercasing) is O(n). The two-pointer comparison is O(n) in the worst case. Both are linear, so total is O(n). We store the cleaned string, which is O(n) space.

Optimization: You could skip the cleaning step and check characters on-the-fly using two pointers with isalnum() checks at each position—this keeps the same Big O but avoids building a new string.