Given a string
s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. For this problem, an empty string is defined as a valid palindrome.Example
s = "A man, a plan, a canal: Panama"
Output: true
After removing non-alphanumeric characters and converting to lowercase, the string becomes "amanaplanacanalpanama", which reads the same forwards and backwards.
Use two pointers starting from both ends of the string, moving inward. Skip over any characters that aren't letters or digits. At each step, compare the lowercase versions of the characters at both pointers — if they ever differ, it's not a palindrome.
Why this works
A palindrome reads the same forwards and backwards. Instead of creating a cleaned copy of the string, use two pointers from each end, skipping non-alphanumeric characters and comparing in lowercase. If every pair matches, it is a palindrome.
Step by step
- Place pointers at both ends — left starts at 0, right starts at the last index.
- Skip non-alphanumeric characters — advance each pointer past spaces, punctuation, etc.
- Compare characters — check if the lowercase versions match; if not, return false.
- Move inward and repeat — continue until the pointers cross; if all pairs matched, return true.
Time: O(n)
Space: O(1)
class Solution {
public boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
left++; // skip non-alphanumeric characters
}
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
right--; // skip non-alphanumeric characters
}
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false; // mismatch means not a palindrome
}
left++;
right--;
}
return true;
}
}
class Solution {
public:
bool isPalindrome(string s) {
int left = 0, right = s.size() - 1;
while (left < right) {
while (left < right && !isalnum(s[left])) {
left++; // skip non-alphanumeric characters
}
while (left < right && !isalnum(s[right])) {
right--; // skip non-alphanumeric characters
}
if (tolower(s[left]) != tolower(s[right])) {
return false; // mismatch means not a palindrome
}
left++;
right--;
}
return true;
}
};
def isPalindrome(s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1 # skip non-alphanumeric characters
while left < right and not s[right].isalnum():
right -= 1 # skip non-alphanumeric characters
if s[left].lower() != s[right].lower(): # case-insensitive compare
return False
left += 1
right -= 1
return True