Valid Palindrome
Asked at Google, Apple
Problem
Given a string, determine if it is a palindrome considering only alphanumeric characters and ignoring cases. This is a classic two-pointer problem that tests string manipulation and edge case handling.
Asked At
| Company | Difficulty | |
|---|---|---|
| Easy | View all Google questions → | |
| Apple | Easy | View all Apple questions → |
How to Think About It
Use two pointers: one at the start, one at the end. Move inward, comparing characters after filtering.
Filter: skip non-alphanumeric characters (advance the pointer). Convert to lowercase for case-insensitive comparison.
The two pointers approach avoids creating a filtered string. You advance pointers in place, which is O(1) space.
Visual walkthrough for "A man, a plan, a canal: Panama":
left=0(A), right=34(a). Both alpha. Lower: a==a. Move in.
left=1( ), skip. left=2(m), right=32(m). m==m. Move in.
left=3(a), right=31(a). a==a. Move in.
left=4(n), right=30(l). Skip colon. n==n... Continue until pointers meet.
Result: true.
Visual walkthrough for "race a car":
left=0(r), right=8(r). r==r. Move in.
left=1(a), right=7(c). a!=c. Return false.
Edge cases: empty string (true), single character (true), all non-alphanumeric (true), mixed case.
Optimal Approach
Step 1: Set left = 0, right = len(s) - 1.
Step 2: While left < right:
- Advance left while s[left] is not alphanumeric
- Advance right while s[right] is not alphanumeric
- If s[left].lower() != s[right].lower(), return false
- Move both pointers inward
Step 3: Return true.
The key insight: you don't need to build a filtered string. Just skip non-alphanumeric characters in place.
Time: O(n) — each character is visited at most once. Space: O(1).
What Trips People Up in Real Interviews
Building a filtered string first. While it works, the two-pointer in-place approach is O(1) space and demonstrates better algorithmic thinking.
Forgetting to handle uppercase. Convert both characters to lowercase (or uppercase) before comparing.
Not skipping non-alphanumeric characters. The problem says to ignore spaces, punctuation, and special characters.
Off-by-one when pointers meet. The loop condition is left < right, not left <= right. When they meet, all pairs have been checked.
Not checking bounds in the inner while loops. Always check left < right before advancing to avoid crossing the pointers.
Solution Code
def isPalindrome(s):
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return TrueFrequently Asked Questions
What is the Valid Palindrome problem?
Given a string, determine if it is a palindrome considering only alphanumeric characters and ignoring cases. This is a classic two-pointer problem that tests string manipulation and edge case handling.
How do you solve Valid Palindrome?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Valid Palindrome?
Valid Palindrome is asked at Google, Apple. It is a easy difficulty problem.
What are common mistakes on Valid Palindrome?
- Building a filtered string first. While it works, the two-pointer in-place approach is `O(1)` space and demonstrates better algorithmic thinking.
- Forgetting to handle uppercase. Convert both characters to lowercase (or uppercase) before comparing.
- Not skipping non-alphanumeric characters. The problem says to ignore spaces, punctuation, and special characters.
- Off-by-one when pointers meet. The loop condition is `left < right`, not `left <= right`. When they meet, all pairs have been checked.
- Not checking bounds in the inner while loops. Always check `left < right` before advancing to avoid crossing the pointers.