Valid Palindrome
Problem
Given a string s, return true if it is a palindrome considering only alphanumeric characters and ignoring cases, otherwise return false.
- 1 ≤ s.length ≤ 2 * 10⁵
- s consists only of printable ASCII characters.
Example
s = "A man, a plan, a canal: Panama"trueThe algorithm uses two pointers starting at the beginning and end of the string. It skips non-alphanumeric characters by advancing the pointers inward until both point to alphanumeric characters. Then it compares the lowercase versions of these characters. If they differ, the string is not a palindrome. Otherwise, it moves both pointers inward and repeats. For the input, all non-alphanumeric characters are ignored, and the remaining characters form a palindrome, so the function returns true.
Approach
Straightforward Solution
A brute-force approach would preprocess the string by removing all non-alphanumeric characters and converting to lowercase, then check if the resulting string is equal to its reverse. This requires extra space proportional to the input size and two passes over the string.
Core Observation
A palindrome reads the same forwards and backwards when considering only alphanumeric characters and ignoring case. This means the problem reduces to comparing characters symmetrically from both ends, skipping irrelevant characters.
Path to Optimal
The key recognition signals are 'palindrome', 'ignoring cases', and 'considering only alphanumeric characters'. These indicate a Two Pointers approach because the problem involves symmetric character comparisons from both ends, and skipping irrelevant characters suggests pointer movement rather than full preprocessing. This approach avoids extra space and performs the check in a single pass.
Optimal Approach
Use two pointers, one at the start and one at the end of the string. Move each pointer inward while skipping non-alphanumeric characters. Compare the lowercase characters at these pointers. If they differ, return false immediately. If they match, move both pointers inward and continue until they cross. If no mismatches are found, return true. This approach runs in O(n) time and O(1) auxiliary space.
Time
O(n)
Each character is visited at most once by either pointer. Skipping non-alphanumeric characters and comparing filtered characters is done in a single pass.
Space
O(1)
Only a fixed number of variables (two pointers and temporary variables for character comparison) are used, with no additional data structures proportional to input size.
Pattern Spotlight
Two Pointers (Symmetric Character Comparison with Filtering)
When verifying palindromes with character filtering, use two pointers moving inward from both ends, skipping irrelevant characters on the fly, and compare only the filtered characters to achieve O(n) time and O(1) space.
Solution
| 1 | class Solution:
|
| 2 | def isPalindrome(self, s: str) -> bool:
|
| 3 | l, r = 0, len(s) - 1
|
| 4 |
|
| 5 | while l < r:
|
| 6 | while l < r and not s[l].isalnum():
|
| 7 | l += 1
|
| 8 | while l < r and not s[r].isalnum():
|
| 9 | r -= 1
|
| 10 |
|
| 11 | if s[l].lower() != s[r].lower():
|
| 12 | return False
|
| 13 |
|
| 14 | l += 1
|
| 15 | r -= 1
|
| 16 |
|
| 17 | return True |
Step-by-Step Solution
Initialize Two Pointers at String Boundaries
| 3 | l, r = 0, len(s) - 1
|
Objective
To set up the initial positions for symmetric comparison from both ends of the string.
Key Insight
Starting pointers at the extreme ends allows the algorithm to compare characters in pairs moving inward, which is the natural approach for palindrome verification. This setup is the foundation for the filtering and comparison logic that follows.
Interview Quick-Check
Core Logic
Two pointers at the start and end enable linear-time symmetric comparison without extra space.
State & Boundaries
Pointers must be valid indices within the string bounds before entering the main loop.
Skip Non-Alphanumeric Characters While Moving Pointers
| 5 | while l < r:
|
| 6 | while l < r and not s[l].isalnum():
|
| 7 | l += 1
|
| 8 | while l < r and not s[r].isalnum():
|
| 9 | r -= 1
|
Objective
To advance pointers inward until they point to alphanumeric characters, ensuring irrelevant characters are ignored.
Key Insight
Filtering characters on the fly avoids the need for preprocessing the string. This dynamic skipping maintains O(1) space and ensures that comparisons are only made between valid characters, preserving correctness under the problem's constraints.
Interview Quick-Check
Core Logic
Use while loops to move pointers past non-alphanumeric characters, ensuring only relevant characters are compared.
Common Pitfalls & Bugs
Failing to check pointer bounds in the skipping loops can cause index errors or infinite loops.
State & Boundaries
The condition l < r ensures pointers do not cross while skipping characters.
Compare Filtered Characters Case-Insensitively and Move Pointers
| 11 | if s[l].lower() != s[r].lower():
|
| 12 | return False
|
| 14 | l += 1
|
| 15 | r -= 1
|
Objective
To verify if the current pair of characters match under case-insensitive comparison and advance pointers inward if they do.
Key Insight
Comparing lowercase versions ensures case insensitivity, a core requirement. Immediate return on mismatch guarantees early termination for non-palindromes, optimizing performance. Moving pointers inward after successful comparison progresses the check towards the center.
Interview Quick-Check
Core Logic
Compare lowercase characters at pointers; if they differ, return false immediately to avoid unnecessary work.
State & Boundaries
Increment left pointer and decrement right pointer only after a successful match to maintain correct traversal.
Common Pitfalls & Bugs
Not converting characters to lowercase before comparison can cause false negatives due to case differences.
Return True After Successful Full Comparison
| 17 | return True |
Objective
To conclude the function by returning true if all character pairs matched, confirming the string is a palindrome.
Key Insight
If the pointers cross without finding mismatches, the string satisfies the palindrome condition under filtering and case insensitivity. Returning true here signals successful verification.
Interview Quick-Check
Core Logic
Returning true after the loop confirms no mismatches were found, validating the palindrome.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
if s[l].lower() != s[r].lower():Compare lowercase characters at left and right pointers.
Case-insensitive comparison is essential to meet the problem's requirement that letter case be ignored when checking palindrome validity.
return FalseReturn false immediately if characters do not match.
Early termination on mismatch prevents unnecessary further checks, optimizing performance and correctness.
l, r = 0, len(s) - 1Initialize left and right pointers at the start and end of the string.
Setting pointers at both ends enables symmetric comparison, which is the fundamental approach to palindrome checking.
while l < r and not s[l].isalnum():Advance left pointer while it points to a non-alphanumeric character and is less than right pointer.
Skipping non-alphanumeric characters on the left side ensures only relevant characters are compared, preserving correctness under filtering.
while l < r and not s[r].isalnum():Advance right pointer while it points to a non-alphanumeric character and is greater than left pointer.
Skipping non-alphanumeric characters on the right side mirrors the left pointer logic, maintaining symmetry and correctness.
return TrueReturn true after all character pairs have been successfully compared.
If no mismatches were found by the time pointers cross, the string satisfies the palindrome condition under the problem's constraints.
l += 1Increment left pointer after successful character match.
Moving the left pointer inward progresses the comparison towards the center of the string.
r -= 1Decrement right pointer after successful character match.
Moving the right pointer inward complements the left pointer movement, maintaining symmetric traversal.
while l < r:Start the main loop that continues while left pointer is less than right pointer.
The loop condition ensures that comparisons proceed inward until pointers meet or cross, covering all character pairs.
l += 1Increment left pointer to skip non-alphanumeric characters.
Incrementing here moves the pointer forward to the next candidate character for comparison.
r -= 1Decrement right pointer to skip non-alphanumeric characters.
Decrementing here moves the pointer backward to the next candidate character for comparison.
Test Your Understanding
Why must the pointers skip non-alphanumeric characters before comparing, and why is it important to compare characters in lowercase?
Skipping non-alphanumeric characters ensures only relevant characters are compared, preserving the palindrome definition under filtering. Comparing lowercase versions ensures case-insensitive matching, as uppercase and lowercase letters should be considered equal.
Related Problems
Two Pointers pattern
Don't just read it. Drill it.
Reconstruct Valid Palindrome from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Start drilling Valid Palindrome for free