Valid Palindrome(#125)
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
Input: race a car
Output: false
Input:
Output: true
🧠 Approach
We need to check if a string is a palindrome, ignoring non-alphanumeric characters and case.
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.
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.
- This avoids building a new array and reduces space usage.
💻 Code
// 🔹 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)