Valid Palindrome

easyFREETwo PointersBlind 75

Given a string s, return True if it is a palindrome after converting all uppercase letters to lowercase and removing all non-alphanumeric characters, or False otherwise.

Example

Input

A man, a plan, a canal: Panama

Output

True

Reasoning

Input: s is a string of printable ASCII characters — here the 30-character sentence "A man, a plan, a canal: Panama", with capitals, spaces, commas and a colon mixed in.
Normalise: only letters and digits count, and case is ignored. Dropping the 9 spaces/punctuation marks and lowering the two capitals leaves a 21-character string $t$ = "amanaplanacanalpanama".
Palindrome condition: with $n = 21$ , $t$ is a palindrome when $t_i = t_{n-1-i}$ for every position $i$ . Pairing them up: $t_0 = t_{20} =$ a, $t_1 = t_{19} =$ m, $t_2 = t_{18} =$ a, … all the way in to $t_9 = t_{11} =$ a.
With an odd length, the middle character $t_{10} =$ c is paired with itself, so it never breaks the match.
Output: every pair agrees, so the answer is True.
Notice the condition is about the cleaned string only: "race a car" becomes "raceacar", where $t_3 =$ e but $t_4 =$ a, giving False; and " " cleans to the empty string, which trivially satisfies the condition, giving True.

Constraints

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

Learn this in

Two Pointers & Sliding WindowDSA Study Plan

More from Blind 75

Alien Dictionaryhard Clone Graphmedium Combination Summedium Word Search IIhard Merge K Sorted Listshard

Concept primer

Background Knowledge

The problem involves determining whether a given string is a palindrome after some preprocessing steps. A palindrome is a sequence that reads the same backward as forward. In the context of strings, this means that if we were to reverse the string, it would be identical to the original. The preprocessing steps include converting all uppercase letters to lowercase and removing all non-alphanumeric characters. This is important because it affects how we compare characters and how we define what constitutes a palindrome in this problem.

Understanding two pointers is crucial for solving this problem efficiently. The two pointers technique involves using two pointers (references to locations in the string) that move towards each other (or sometimes away from each other) based on certain conditions. This technique is particularly useful for problems that require comparing elements from the start and end of a sequence, which is the case for palindromes.

The concept of alphanumeric characters is also key. Alphanumeric characters are those that are either letters (both uppercase and lowercase) or numbers. In the context of this problem, we are only interested in these characters because the problem statement specifies that all non-alphanumeric characters should be ignored. This means we need a way to identify and filter out non-alphanumeric characters from the string.

Algorithm/Approach

The general approach to solving this type of problem involves using the two pointers technique to compare characters from the start and end of the string, moving towards the center. This approach allows for an efficient comparison of characters without needing to reverse the entire string or use additional data structures that would increase memory usage.

Step-by-Step Strategy

Initialize two pointers, one at the start of the string (left) and one at the end (right).
Move the pointers towards each other, comparing the characters at the left and right positions.
Before comparing, ensure that both characters are alphanumeric and convert them to lowercase for case-insensitive comparison.
If a non-alphanumeric character is encountered at either the left or right position, move the corresponding pointer towards the center until an alphanumeric character is found.
If at any point the characters at the left and right positions do not match after preprocessing, return False.
Continue this process until the pointers meet or cross each other. If the loop completes without finding any mismatches, return True, indicating that the string is a palindrome after preprocessing.

Common Pitfalls

Forgetting to convert characters to lowercase before comparison.
Not properly handling non-alphanumeric characters, such as not moving the pointers past them correctly.
Incorrectly initializing or moving the pointers, which can lead to incorrect comparisons or infinite loops.

Time & Space Complexity

Time Complexity: $O(n)$ , where $n$ is the length of the string, because in the worst case, we might need to traverse the entire string once.
Space Complexity: $O(1)$ , because we are only using a constant amount of space to store the pointers and do not use any data structures that scale with the input size.

solution.py

Python 3.13

Test results