Valid Palindrome
Check if a string is a palindrome after removing non-alphanumeric characters and ignoring case.
Problem statement
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
Example 1
Input: s = "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama" is a palindrome.
Example 2
Input: s = "race a car" Output: false Explanation: "raceacar" is not a palindrome.
Interactive visualizer
See the two pointers move step by step.
Approach: two pointers
- 1Initialize two pointers:
leftat the start andrightat the end. - 2While
left < right:- Skip non-alphanumeric characters on both sides
- Compare characters (case-insensitive)
- If they differ, return false
- Move both pointers inward
- 3If all characters match, return true.
Key insights
- The two pointers technique efficiently checks from both ends simultaneously.
- In-place comparison without creating a new string saves memory.
- Case-insensitive comparison uses toLowerCase() or character code comparison.
- Regular expressions can filter alphanumeric characters, but two pointers is more efficient.
Solution
function isPalindrome(s: string): boolean {
let left = 0;
let right = s.length - 1;
while (left < right) {
// Skip non-alphanumeric from left
while (left < right && !isAlphanumeric(s[left])) {
left++;
}
// Skip non-alphanumeric from right
while (left < right && !isAlphanumeric(s[right])) {
right--;
}
// Compare characters (case-insensitive)
if (s[left].toLowerCase() !== s[right].toLowerCase()) {
return false;
}
left++;
right--;
}
return true;
}
function isAlphanumeric(char: string): boolean {
return /[a-zA-Z0-9]/.test(char);
}Time & space complexity
Time complexity
O(n)
Single pass through the string
Space complexity
O(1)
Only two pointers are used
Related problems
Longest Palindromic Substring
Coming soonFind the longest palindrome within a string.
Valid Palindrome II
Coming soonCheck for a palindrome when at most one character may be deleted.
Palindrome Linked List
Coming soonCheck if a linked list is a palindrome.
Discussion
Questions, ideas or a different approach? Join the conversation.