ASCII Palindrome Checker

You're in a Meta phone screen, and the interviewer types a string into the shared editor: "A man, a plan, a canal: Panama". "Is this a palindrome?" they ask. You pause for a second. There are spaces, commas, a colon, and mixed casing. But once you strip all that away and lowercase everything, you get amanaplanacanalpanama, which reads the same in both directions. This is the Valid Palindrome problem, and Meta asks it more frequently than almost any other string question. On Firecode, we call it "ASCII Palindrome Checker," and it tests whether you can handle string cleanup and two-pointer traversal in a single, clean pass.

TL;DR

Use two pointers starting at opposite ends of the string. Skip non-alphanumeric characters with inner loops, then compare the lowercased characters at each pointer. If every pair matches until the pointers meet, the string is a palindrome. This runs in O(n) time with O(1) space. The key detail is checking left < right inside the skip loops to avoid out-of-bounds access on strings that are entirely non-alphanumeric.

Why This Problem Matters

Valid Palindrome shows up constantly in technical interviews because it packs several core skills into a small problem. You need to traverse a string with two pointers, filter characters on the fly, handle case normalization, and manage boundary conditions - all without allocating extra memory. It's the kind of problem that separates candidates who understand in-place string processing from those who reach for built-in library methods that sidestep the real challenge.

Understanding the Problem

Here's what we're working with:

Given: A string s of printable ASCII characters Return: true if s is a palindrome after removing all non-alphanumeric characters and converting to lowercase, false otherwise

A few examples to ground the discussion:

• "A man, a plan, a canal: Panama" becomes "amanaplanacanalpanama" after filtering. Reads the same forwards and backwards. Returns true.
• "race a car" becomes "raceacar". Not the same reversed. Returns false.
• " " has no alphanumeric characters at all. With nothing to compare, it's trivially a palindrome. Returns true.

Constraints:

• 1 <= s.length <= 1000
• s consists only of printable ASCII characters

Edge Cases Worth Noting

1. All non-alphanumeric: A string like " " or "!@#$" has no characters to compare, so it is a palindrome
2. Single character: "a" is always a palindrome
3. Numeric strings: "12321" is a palindrome since digits are alphanumeric
4. Mixed case: "Aa" is a palindrome because 'A' and 'a' match after lowercasing

Solution Approach

The brute-force way would be to create a new string containing only the lowercase alphanumeric characters, then check if that string equals its reverse. That works, but it costs O(n) extra space for the filtered string and another O(n) for the reversed copy.

A better approach is to work directly on the original string with two pointers. Place left at index 0 and right at the last index. Move them toward each other, skipping over any character that isn't a letter or digit. When both pointers land on alphanumeric characters, compare them (case-insensitively). If they ever differ, return false. If the pointers cross without a mismatch, return true.

Why Two Pointers Work Here

A palindrome reads identically from both ends. By comparing the outermost valid characters first and working inward, you're checking the palindrome property in the most direct way possible. The skip loops handle the "ignore non-alphanumeric" requirement without building a separate filtered string.

The diagram above traces the pointer movement for "A man, a plan, a canal: Panama". The pointers start at opposite ends, skip punctuation and spaces, compare lowercase characters, and converge toward the center.

Handling Non-Alphanumeric Characters

The inner skip loops are the detail that trips up most candidates. When advancing left past a colon or space, you still need to check that left < right at every step. Otherwise, a string like ".,," would cause the left pointer to overshoot.

Case-Insensitive Comparison

After finding alphanumeric characters at both pointers, convert each to lowercase before comparing. This is straightforward in every language, but forgetting it is a common source of bugs.

When Characters Don't Match

For "race a car", the filtered version is "raceacar". The outer characters match (r and r), then the next pair matches (a and a), then c and c, but then we hit e versus a. That mismatch triggers an immediate false return.

Numeric Palindromes

Digits count as alphanumeric, so "12321" is checked the same way. No case conversion is needed for digits, but the lowercasing operation is harmless on them.

The Empty-After-Filter Case

A string with no alphanumeric characters, like " ", produces an interesting scenario. The left pointer skips past every character and crosses the right pointer. Since no mismatch was found, the function returns true.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public boolean isPalindrome(String s) {
    int left = 0;
    int right = s.length() - 1;

    while (left < right) {
      // Skip non-alphanumeric from the left
      while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
        left++;
      }
      // Skip non-alphanumeric from the right
      while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
        right--;
      }
      // Compare lowercased characters
      if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
        return false;
      }
      left++;
      right--;
    }

    return true;
  }
}

Walk through this with "A man, a plan, a canal: Panama":

Iteration 1:

• left=0 is 'A' (alphanumeric), right=29 is 'a' (alphanumeric)
• toLowerCase('A') == toLowerCase('a') -> 'a' == 'a', match
• Move: left=1, right=28

Iteration 2:

• left=1 is ' ' (not alphanumeric), skip to left=2 which is 'm'
• right=28 is 'm' (alphanumeric)
• 'm' == 'm', match
• Move: left=3, right=27

This continues, with both pointers skipping past commas, spaces, and the colon, matching a, n, a, p, l, and so on until the pointers meet in the middle.

Complexity Analysis

Time Complexity: O(n)

Each pointer traverses the string at most once. The left pointer only moves right, and the right pointer only moves left. Even with the inner skip loops, every character is visited at most once per pointer, giving a total of at most 2n character accesses. That simplifies to O(n).

Space Complexity: O(1)

The algorithm uses two integer pointers and no auxiliary data structures. No new strings are created, no arrays are allocated. The space usage is constant regardless of input size.

Comparison with Alternative Approaches

The two-pointer approach is optimal in both time and space. In an interview, mentioning the filter-and-reverse approach as a simpler alternative before presenting the O(1) space solution shows good engineering judgment.

Common Pitfalls

1. Missing the inner boundary check: Writing while (!Character.isLetterOrDigit(s.charAt(left))) without left < right causes index-out-of-bounds on strings that are all punctuation.

2. Forgetting case normalization: Comparing 'A' directly with 'a' returns false. Always lowercase (or uppercase) both characters before comparing.

3. Using built-in reverse: Some candidates write new StringBuilder(filtered).reverse().toString().equals(filtered). This works but uses O(n) space and doesn't demonstrate understanding of the two-pointer technique.

4. Off-by-one on pointer movement: Forgetting to advance left++ and right-- after a successful comparison creates an infinite loop.

5. Not treating digits as alphanumeric: The problem specifies that letters AND numbers are alphanumeric. "12321" should return true.

Interview Tips

When you get this problem in an interview:

1. Clarify the definition: Ask whether spaces and punctuation should be ignored, and whether the check is case-insensitive. The answer is almost always yes to both, but confirming shows thoroughness.

2. Start with the brute force: Briefly mention the filter-reverse-compare approach, note its O(n) space cost, then pivot to the two-pointer solution.

3. Trace through an example: Walk through "race a car" on the whiteboard. It's short enough to trace completely and demonstrates the early exit on mismatch.

4. Call out the skip loop guard: Explicitly mention that the left < right check inside the skip loops prevents out-of-bounds access. Interviewers notice this attention to detail.

5. Prepare for follow-ups:

   • "What if you could remove at most one character?" (Valid Palindrome II)
   • "What if the input is a linked list?" (Palindrome Linked List)
   • "What about finding the longest palindromic substring?" (Different technique entirely)

Key Takeaways

• The two-pointer technique checks palindrome properties in O(n) time and O(1) space by comparing characters from both ends moving inward.
• Inner skip loops handle non-alphanumeric characters without creating a filtered copy. Always guard them with left < right to prevent out-of-bounds access.
• Case normalization is a one-line addition per language (toLowerCase, .lower(), std::tolower) but forgetting it is one of the most common bugs in interviews.
• This problem combines string traversal, character classification, and boundary management into a compact package that appears frequently at Meta, Yandex, Adobe, Amazon, and Google.
• The filter-and-reverse approach is acceptable as a first pass, but interviewers at top companies expect the O(1) space two-pointer solution.

Solutions in Other Languages

Python

class Solution:
    def is_palindrome(self, s: str) -> bool:
        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

Python's str.isalnum() handles both letters and digits. The .lower() method on a single character returns its lowercase equivalent.

JavaScript

class Solution {
  isPalindrome(s) {
    let left = 0;
    let right = s.length - 1;

    while (left < right) {
      while (left < right && !this.isAlphanumeric(s[left])) {
        left++;
      }
      while (left < right && !this.isAlphanumeric(s[right])) {
        right--;
      }
      if (s[left].toLowerCase() !== s[right].toLowerCase()) {
        return false;
      }
      left++;
      right--;
    }

    return true;
  }

  isAlphanumeric(char) {
    return /[a-zA-Z0-9]/.test(char);
  }
}

JavaScript lacks a built-in isAlphanumeric method, so a regex test against [a-zA-Z0-9] is the standard workaround.

TypeScript

class Solution {
  isPalindrome(s: string): boolean {
    let left = 0;
    let right = s.length - 1;

    while (left < right) {
      while (left < right && !this.isAlphanumeric(s[left])) {
        left++;
      }
      while (left < right && !this.isAlphanumeric(s[right])) {
        right--;
      }
      if (s[left].toLowerCase() !== s[right].toLowerCase()) {
        return false;
      }
      left++;
      right--;
    }

    return true;
  }

  private isAlphanumeric(char: string): boolean {
    return /[a-zA-Z0-9]/.test(char);
  }
}

C++

#include <string>
#include <cctype>

class Solution {
public:
  bool isPalindrome(std::string &s) {
    int left = 0;
    int right = s.size() - 1;

    while (left < right) {
      while (left < right && !std::isalnum(s[left])) {
        ++left;
      }
      while (left < right && !std::isalnum(s[right])) {
        --right;
      }
      if (std::tolower(s[left]) != std::tolower(s[right])) {
        return false;
      }
      ++left;
      --right;
    }

    return true;
  }
};

C++ uses std::isalnum() and std::tolower() from <cctype>. The string is passed by reference to avoid copying.

Go

package solution

import "unicode"

func (sol *Solution) IsPalindrome(s string) bool {
    left, right := 0, len(s)-1

    for left < right {
        for left < right && !isAlphanumeric(rune(s[left])) {
            left++
        }
        for left < right && !isAlphanumeric(rune(s[right])) {
            right--
        }
        if unicode.ToLower(rune(s[left])) != unicode.ToLower(rune(s[right])) {
            return false
        }
        left++
        right--
    }

    return true
}

func isAlphanumeric(r rune) bool {
    return unicode.IsLetter(r) || unicode.IsDigit(r)
}

Go uses the unicode package for character classification and case conversion. Characters are cast to rune for proper Unicode handling.

Scala

class Solution {
  def isPalindrome(s: String): Boolean = {
    var left = 0
    var right = s.length - 1

    while (left < right) {
      while (left < right && !s.charAt(left).isLetterOrDigit) {
        left += 1
      }
      while (left < right && !s.charAt(right).isLetterOrDigit) {
        right -= 1
      }
      if (s.charAt(left).toLower != s.charAt(right).toLower) {
        return false
      }
      left += 1
      right -= 1
    }

    true
  }
}

Kotlin

class Solution {
  fun isPalindrome(s: String): Boolean {
    var left = 0
    var right = s.length - 1

    while (left < right) {
      while (left < right && !s[left].isLetterOrDigit()) {
        left++
      }
      while (left < right && !s[right].isLetterOrDigit()) {
        right--
      }
      if (s[left].lowercaseChar() != s[right].lowercaseChar()) {
        return false
      }
      left++
      right--
    }

    return true
  }
}

Swift

import Foundation

class Solution {
    func isPalindrome(_ s: String) -> Bool {
        let chars = Array(s)
        var left = 0
        var right = chars.count - 1

        while left < right {
            while left < right && !chars[left].isLetter && !chars[left].isNumber {
                left += 1
            }
            while left < right && !chars[right].isLetter && !chars[right].isNumber {
                right -= 1
            }
            if chars[left].lowercased() != chars[right].lowercased() {
                return false
            }
            left += 1
            right -= 1
        }

        return true
    }
}

Swift converts the string to an Array of Character for O(1) index access, since Swift strings don't support random access by default.

Rust

pub struct Solution;

impl Solution {
    pub fn is_palindrome(&self, s: String) -> bool {
        let bytes = s.as_bytes();
        let mut left = 0i32;
        let mut right = bytes.len() as i32 - 1;

        while left < right {
            while left < right && !(bytes[left as usize] as char).is_alphanumeric() {
                left += 1;
            }
            while left < right && !(bytes[right as usize] as char).is_alphanumeric() {
                right -= 1;
            }
            if (bytes[left as usize] as char).to_ascii_lowercase()
                != (bytes[right as usize] as char).to_ascii_lowercase()
            {
                return false;
            }
            left += 1;
            right -= 1;
        }

        true
    }
}

Rust works with the byte slice for efficient access. Since the problem guarantees ASCII-only input, the as char cast is safe.

Ruby

class Solution
  def palindrome?(s)
    left = 0
    right = s.length - 1

    while left < right
      while left < right && !s[left].match?(/[a-zA-Z0-9]/)
        left += 1
      end
      while left < right && !s[right].match?(/[a-zA-Z0-9]/)
        right -= 1
      end
      return false if s[left].downcase != s[right].downcase
      left += 1
      right -= 1
    end

    true
  end
end

C#

public class Solution {
    public bool isPalindrome(string s) {
        int left = 0;
        int right = s.Length - 1;

        while (left < right) {
            while (left < right && !char.IsLetterOrDigit(s[left])) {
                left++;
            }
            while (left < right && !char.IsLetterOrDigit(s[right])) {
                right--;
            }
            if (char.ToLower(s[left]) != char.ToLower(s[right])) {
                return false;
            }
            left++;
            right--;
        }

        return true;
    }
}

PHP

class Solution {
    public function isPalindrome(string $s): bool {
        $left = 0;
        $right = strlen($s) - 1;

        while ($left < $right) {
            while ($left < $right && !ctype_alnum($s[$left])) {
                $left++;
            }
            while ($left < $right && !ctype_alnum($s[$right])) {
                $right--;
            }
            if (strtolower($s[$left]) !== strtolower($s[$right])) {
                return false;
            }
            $left++;
            $right--;
        }

        return true;
    }
}

Dart

class Solution {
  bool isPalindrome(String s) {
    int left = 0;
    int right = s.length - 1;

    while (left < right) {
      while (left < right && !_isAlphanumeric(s[left])) {
        left++;
      }
      while (left < right && !_isAlphanumeric(s[right])) {
        right--;
      }
      if (s[left].toLowerCase() != s[right].toLowerCase()) {
        return false;
      }
      left++;
      right--;
    }

    return true;
  }

  bool _isAlphanumeric(String char) {
    int code = char.codeUnitAt(0);
    return (code >= 48 && code <= 57) ||
           (code >= 65 && code <= 90) ||
           (code >= 97 && code <= 122);
  }
}

Practice and Next Steps

Once palindrome checking feels natural, these related problems will deepen your two-pointer skills:

• Valid Palindrome II - Can you make it a palindrome by removing at most one character?
• Palindrome Linked List - Check the palindrome property on a linked list in O(1) space
• Longest Palindromic Substring - Find the longest palindromic contiguous substring

This problem and thousands of others are available on Firecode, where over 50,000 users have prepared for technical interviews and landed offers at top tech companies. Consistent practice with problems like this builds the pattern recognition that makes interview day feel routine instead of stressful.