Katkat
Back

Check a Palindrome While Ignoring Case and Punctuation

AmazonSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Tests string manipulation and two-pointer traversal techniques to verify if a string is a palindrome while ignoring non-alphanumeric characters and case.

Problem Statement

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include standard ASCII letters (a-z, A-Z) and digits (0-9).

Given a string s, return True if it is a palindrome, or False otherwise.

Aim to solve this in O(n) time and O(1) auxiliary space.

Function Signature

def is_palindrome(s: str) -> bool:
    pass

Examples

Example 1

Input: s = "A man, a plan, a canal: Panama"
Output: True
Explanation: After removing non-alphanumeric characters and converting to lowercase, the string becomes "amanaplanacanalpanama", which reads the same backward and forward.

Example 2

Input: s = "race a car"
Output: False
Explanation: After cleaning, the string becomes "raceacar", which is not a palindrome.

Example 3

Input: s = " "
Output: True
Explanation: An empty string or a string with only non-alphanumeric characters becomes "" after cleaning, which is trivially a palindrome.

Constraints

  • 1 <= len(s) <= 2 * 10^5
  • s consists only of printable ASCII characters.

Edge Cases to Consider

  • The string contains only whitespace or punctuation characters.
  • Digits mixed with letters (e.g., "0P" should return False).
  • A single character string.

Hints

Hint 1

A two-pointer approach starting from both ends allows you to check characters without allocating a new filtered string.

Hint 2

Whenever a pointer encounters a non-alphanumeric character, simply increment or decrement it until it points to a valid letter or digit.

Hint 3

Compare the characters at both pointers after converting them to lowercase; if they mismatch, return False immediately.

Follow-up questions

  • How would you adapt the solution if you are allowed to remove at most one character to make the string a palindrome?
  • How would your approach change if the input contains full Unicode characters (e.g., accented characters or non-Latin alphabets)?
  • How would you handle this check if the input is provided as a streaming sequence of characters that cannot all fit into memory at once?