Quick Overview

Check whether a string is a palindrome after ignoring punctuation and letter case while retaining ASCII letters and digits.

Check a Palindrome While Ignoring Case and Punctuation

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

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 ```text s = "A1, bB!1a" Output: true ``` The retained sequence, ignoring case, is `a1bb1a`. ### Example 2 ```text s = "0P" Output: false ``` The digit is retained, so the normalized sequence is `0p`.

Overview: Check whether a string is a palindrome after ignoring punctuation and letter case while retaining ASCII letters and digits.

Read the full Amazon Software Engineer interview experience this question came from

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 ```text s = "A1, bB!1a" Output: true ``` The retained sequence, ignoring case, is `a1bb1a`. ### Example 2 ```text s = "0P" Output: false ``` The digit is retained, so the normalized sequence is `0p`.

Constraints

  • s contains printable ASCII characters with codes 32 through 126.
  • 0 <= s.length <= 200000.
  • Retain only A-Z, a-z and 0-9. Compare letters without regard to case.
  • An empty retained sequence is a palindrome.

Examples

Input: ('A1, bB!1a',)

Expected Output: True

Explanation: Published sample 1: the retained sequence is a1bb1a.

Input: ('0P',)

Expected Output: False

Explanation: Published sample 2: the digit and letter remain distinct.

Loading coding console...

Show the approach

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.