Check a Palindrome While Ignoring Case and Punctuation

Implement isPalindrome(s). Keep only ASCII letters and digits from the string, compare letters without regard to case, and return whether the remaining sequence reads the same forward and backward.

Rules and Constraints

• Letters are A through Z and a through z; digits are 0 through 9.
• Ignore spaces, punctuation, and all other characters in the supplied printable ASCII string.
• A sequence with no retained characters is a palindrome.
• 0 <= s.length <= 200,000. This practice version also accepts an empty input string.

Example 1

s = "A1, bB!1a"
Output: true

The retained sequence, ignoring case, is a1bb1a.

Example 2

s = "0P"
Output: false

The digit is retained, so the normalized sequence is 0p.

Check a Palindrome While Ignoring Case and Punctuation

Approach

Use two indices, initially at the beginning and end of the original string. Classify each inspected character with explicit ASCII ranges. Convert uppercase letters to their lowercase code; preserve lowercase letters and digits; mark everything else as ignored.

If either endpoint is ignored, move only that index inward. Otherwise these are the first and last retained characters still under consideration. Return false if their normalized codes differ; if they agree, move both indices inward. Return true when the indices meet or cross.

The invariant is that every retained character outside the current interval has already been paired with an equal retained character on the opposite side. Skipping an ignored character does not change the retained sequence. A differing endpoint pair disproves symmetry; an equal pair reduces the same question to the interior. Once at most one position remains, all required pairs match. This also covers empty input and strings containing no letters or digits.

Each index moves inward at most n times, so the algorithm takes O(n) time and O(1) auxiliary space. The C++ callable receives its string by value as declared in the public starter; that interface can copy O(n) input storage, separately from the O(1) working state.

• Time complexity: O(n), where n is the input length.
• Space complexity: O(1) auxiliary working space; the C++ by-value string parameter may copy O(n) input storage.