Valid Palindrome
(#125), Easy
Category: String, Two Pointer
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.
Examples
Input: A man, a plan, a canal: Panama
Output: true
Explanation: After cleaning and lowering the string, we get 'amanaplanacanalpanama', which is a palindrome.
Input: race a car
Output: false
Explanation: After cleaning and lowering the string, we get 'raceacar', which is not a palindrome.
Input:
Output: true
Explanation: After cleaning, the string is empty. An empty string is considered a valid palindrome.
Approach
Approach 1: Brute Force
- Filter the string to keep only alphanumeric characters.
- Convert the string to lowercase.
- Use two pointers to compare characters from the start and end.
- If all pairs match, return true. Else, return false.
// 🔹 Brute Force
var isPalindrome = function(s) {
let cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, '');
let start = 0;
let end = cleaned.length - 1;
while (start < end) {
if (cleaned[start] !== cleaned[end]) return false;
start++;
end--;
}
return true;
};Approach 2: Optimized Two Pointer (In-place)
- Use two pointers from the start and end.
- Skip non-alphanumeric characters.
- Compare characters in lowercase on the fly.
- If mismatch found, return false.
- If loop completes, return true.
// 🔹 Optimized In-Place Two Pointer Approach
var isPalindrome = function (s) {
let start = 0;
let end = s.length - 1;
while (start < end) {
while (start < end && !isAlphaNumeric(s[start])) start++;
while (start < end && !isAlphaNumeric(s[end])) end--;
if (s[start].toLowerCase() !== s[end].toLowerCase()) {
return false;
}
start++;
end--;
}
return true;
};
function isAlphaNumeric(c) {
let code = c.charCodeAt(0);
return (
(code >= 48 && code <= 57) || // 0-9
(code >= 65 && code <= 90) || // A-Z
(code >= 97 && code <= 122) // a-z
);
}Complexity
Time: O(n)
Space: O(1)