Approach Summary
Two pointers from both ends. Skip non-alphanumeric characters. Compare lowercased characters.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Clean Alphanumeric String and Reverse Comparison | O(n) | O(n) | Filter out punctuation and spaces into lowercase string; compare mirrored indices. |
| 2 Approach 2: Two Pointers In-Place (Optimal) | O(n) | O(1) | Use left and right pointers directly on s, skipping non-alphanumeric characters in O(1) space. |
Step 1: Baseline
Approach 1: Clean Alphanumeric String and Reverse Comparison
Time: O(n)
Space: O(n)
Scan the input string s once. Collect only letters and numbers, lowercasing uppercase characters into a cleaned string str. Then check if str[i] == str[str.length - 1 - i] for all i up to half its length.
Approach 1: Clean Alphanumeric String and Reverse Comparison Implementation
Approach 1: Clean Alphanumeric String and Reverse Comparison
class Solution {
public boolean isPalindrome(String s) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isLetterOrDigit(c)) {
sb.append(Character.toLowerCase(c));
}
}
int left = 0, right = sb.length() - 1;
while (left <= right) {
if (sb.charAt(left) != sb.charAt(right)) return false;
left++;
right--;
}
return true;
}
}class Solution {
public:
bool isPalindrome(string s) {
string str = "";
for (char c : s) {
if (isalnum(c)) str += tolower(c);
}
for (int i = 0; i < str.size() / 2; i++) {
if (str[i] != str[str.size() - 1 - i]) return false;
}
return true;
}
};class Solution:
def isPalindrome(self, s: str) -> bool:
cleaned = [c.lower() for c in s if c.isalnum()]
return cleaned == cleaned[::-1]function isPalindrome(s) {
const cleaned = s.replace(/[^a-zA-Z0-9]/g, '').toLowerCase();
for (let i = 0; i < Math.floor(cleaned.length / 2); i++) {
if (cleaned[i] !== cleaned[cleaned.length - 1 - i]) return false;
}
return true;
} Step 2: Most Optimized
Approach 2: Two Pointers In-Place (Optimal)
Time: O(n)
Space: O(1)
Start left at 0 and right at len(s) - 1. While left < right: if s[left] is not alphanumeric, left++. If s[right] is not alphanumeric, right--. Once both point to alphanumeric characters, compare them case-insensitively. If they differ, return false; otherwise increment left and decrement right.
Approach 2: Two Pointers In-Place (Optimal) Implementation
Approach 2: Two Pointers In-Place (Optimal)
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++;
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
}
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++;
while (left < right && !isalnum(s[right])) right--;
if (tolower(s[left]) != tolower(s[right])) return false;
left++;
right--;
}
return true;
}
};class Solution:
def isPalindrome(self, s: str) -> bool:
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 Truefunction isPalindrome(s) {
let left = 0, right = s.length - 1;
while (left < right) {
while (left < right && !/[a-zA-Z0-9]/.test(s[left])) left++;
while (left < right && !/[a-zA-Z0-9]/.test(s[right])) right--;
if (s[left].toLowerCase() !== s[right].toLowerCase()) return false;
left++;
right--;
}
return true;
}Edge Cases to Watch
- Empty string or string with only spaces/punctuation (e.g. " .,." -> cleaned is ""; returns true)
- Single alphanumeric character (returns true)
- Mixed case palindrome (e.g. "A man, a plan, a canal: Panama"; returns true)
- Digits included (e.g. "0P" is not a palindrome; "ab_a" -> returns true)
Algorithmic Pattern
View Pattern Guide →
Master the Two Pointers Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Two Pointers pattern.
Framework: Two Pointers • Interview Prep: Tested at FAANG •
Explore all Two Pointers problems & invariants →
How to Recognize This Pattern
- Palindrome check with special characters
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
Tags
String Two Pointers
Frequently Asked Questions
What is the optimal time and space complexity for Valid Palindrome?
The optimal solution for Valid Palindrome achieves O(n) runtime complexity and requires O(1) auxiliary space. Time complexity is O(n) as each character is examined at most twice. Space complexity is O(1) auxiliary space for the two-pointer in-place method, or O(n) for the filtered string method.
How do I identify that Valid Palindrome requires the Two Pointers pattern?
In technical interviews, look for key problem signals: Palindrome check with special characters. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Two Pointers strategy.
What critical edge cases must be handled in Valid Palindrome?
Essential edge cases to verify include: Empty string or string with only spaces/punctuation (e.g. " .,." -> cleaned is ""; returns true); Single alphanumeric character (returns true); Mixed case palindrome (e.g. "A man, a plan, a canal: Panama"; returns true); Digits included (e.g. "0P" is not a palindrome; "ab_a" -> returns true). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Valid Palindrome?
Valid Palindrome is a Easy-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Facebook, Microsoft, Amazon.