Practice/Meta/Leetcode 125. Valid Palindrome

Leetcode 125. Valid Palindrome

CodingMust

Problem

Given a string, determine if it becomes a palindrome after performing two preprocessing steps: converting all uppercase letters to lowercase and removing all non-alphanumeric characters (keeping only letters and digits).

A palindrome is a sequence that reads the same forwards and backwards.

Requirements

1. Only consider alphanumeric characters (letters and digits)
2. Ignore letter casing when comparing characters
3. Return true if the processed string is a palindrome, false otherwise
4. Handle empty strings and strings with no alphanumeric characters (both should return true)

Constraints

• 1 ≤ s.length ≤ 100,000
• The string consists of printable ASCII characters
• Aim for O(n) time complexity and O(1) extra space complexity (excluding the input)

Examples

Example 1:

Input: s = "racecar" Output: true Explanation: The string is already lowercase and alphanumeric, and reads the same forwards and backwards.

Example 2:

Input: s = "A man, a plan, a canal: Panama" Output: true Explanation: After removing spaces and punctuation and converting to lowercase: "amanaplanacanalpanama" which is a palindrome.

Example 3:

Input: s = "hello world" Output: false Explanation: After cleaning: "helloworld" which is not a palindrome.

Example 4:

Input: s = " " Output: true Explanation: After removing non-alphanumeric characters, we have an empty string which is considered a palindrome.