Welcome to Day 6 of the Tekraze DSA series, where we solve the Valid Palindrome problem with the two pointer pattern. So far we leaned hard on hash maps and sets, from Day 1 Two Sum to Day 5 Group Anagrams. Today we pick up a tool that needs no extra memory at all. Valid Palindrome is the friendliest way to learn it, and once it clicks you will see it in dozens of other problems.
Also Read: Missed the hashing days? Start with Valid Anagram and Group Anagrams first.
What is the Valid Palindrome problem?
You get a string s. After converting all uppercase letters to lowercase and removing every character that is not a letter or a digit, check whether it reads the same forward and backward. Return true if it does and false otherwise. This is the classic Valid Palindrome problem on LeetCode.
text
Input: s = "A man, a plan, a canal: Panama"
Output: true (cleaned it becomes "amanaplanacanalpanama")
Input: s = "race a car"
Output: false ("raceacar" is not the same reversed)
Input: s = " "
Output: true (an empty string counts as a palindrome)
How should you think about it in plain words?
Picture two friends reading the same sentence, one starting from the first letter and the other from the last. They step toward each other one letter at a time.
If they ever read different letters, it is not a palindrome. If they meet in the middle without a mismatch, it is. Spaces and punctuation are just noise, so each friend simply skips over them.
What does the brute force solution look like?
The obvious Valid Palindrome solution is to build a cleaned copy of the string, reverse it, and compare the two.
python
def is_palindrome_simple(s):
cleaned = [c.lower() for c in s if c.isalnum()]
return cleaned == cleaned[::-1]
Time is O(n) because we touch each character a few times. Space is O(n) because we store the cleaned copy and its reverse. It is honestly fine for most interviews, but the interviewer will usually ask if you can do it without the extra memory.
How do we get the optimal Valid Palindrome solution?
Use two indexes on the original string. left starts at 0 and right starts at the last position. Move left forward past anything that is not a letter or digit, and move right backward the same way.
Then compare the two characters in lowercase. If they differ, return false. If they match, step both inward and repeat until they cross.
Time is O(n), because every character is visited at most once by one of the pointers. Space is O(1), because we only keep two integers. That is the same speed as the simple version but with no extra copy, which is the whole point of two pointers. If O(1) space still feels fuzzy, our Big O helper post explains time and space complexity with examples.
Java solution for Valid Palindrome
java
public class Solution {
public static 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;
}
public static void main(String[] args) {
String[] inputs = {"A man, a plan, a canal: Panama", "race a car", " ", "0P", "ab_a", "Madam", ""};
boolean[] want = {true, false, true, false, true, true, true};
for (int i = 0; i < inputs.length; i++) {
boolean got = isPalindrome(inputs[i]);
System.out.println((got == want[i] ? "PASS " : "FAIL ") + "\"" + inputs[i] + "\" " + got);
}
}
}
Java’s Character.isLetterOrDigit does the “keep only letters and digits” check for us.
Python solution for Valid Palindrome
python
def is_palindrome(s):
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 True
if __name__ == "__main__":
tests = [
("A man, a plan, a canal: Panama", True),
("race a car", False),
(" ", True),
("0P", False),
("ab_a", True),
("Madam", True),
("", True),
]
for s, want in tests:
got = is_palindrome(s)
print("PASS" if got == want else "FAIL", repr(s), got)
Python’s str.isalnum returns True for letters and digits, so the logic reads almost like the plain-words version.
Rust solution for Valid Palindrome
rust
fn is_palindrome(s: &str) -> bool {
let b = s.as_bytes();
if b.is_empty() {
return true;
}
let (mut left, mut right) = (0usize, b.len() - 1);
while left < right {
while left < right && !b[left].is_ascii_alphanumeric() {
left += 1;
}
while left < right && !b[right].is_ascii_alphanumeric() {
right -= 1;
}
if b[left].to_ascii_lowercase() != b[right].to_ascii_lowercase() {
return false;
}
left += 1;
right -= 1;
}
true
}
fn main() {
let tests = [
("A man, a plan, a canal: Panama", true),
("race a car", false),
(" ", true),
("0P", false),
("ab_a", true),
("Madam", true),
("", true),
];
for (s, want) in tests {
let got = is_palindrome(s);
println!("{} {:?} {}", if got == want { "PASS" } else { "FAIL" }, s, got);
}
}
All three programs were run against the same seven tests: the classic Panama sentence, race a car, a single space, the tricky “0P” case, a string with an underscore, a mixed case word and an empty string. Every one passed. The Rust version also guards the empty string so the right index never underflows. Rust’s is_ascii_alphanumeric is the matching check there.
One difference worth knowing: Java and Python treat accented and non-English letters as letters, but the Rust version only keeps ASCII ones. That matches the LeetCode version of the problem, which uses printable ASCII input. For real multilingual text you would loop over chars() instead of bytes.
What are the 6 best tips for an easy Valid Palindrome solution?
- Spot the pattern. When a problem like Valid Palindrome compares the start and end of something, or asks about symmetry, reach for two pointers moving inward.
- Keep the inner skip loops guarded. Always check
left < rightinside the skip loops, otherwise a string full of punctuation can push a pointer out of range. - Lowercase at compare time. There is no need to build a new string. Convert just the two characters you are comparing.
- Remember digits count. The problem says alphanumeric, so “0P” must return
false. Many people only check letters. - Start simple in interviews. Say the clean and reverse idea out loud first, then offer the two pointer version as the O(1) space upgrade.
- Know the follow up. Valid Palindrome II lets you delete one character. It is the same two pointers, and on the first mismatch you try skipping either side once.
What are the common mistakes people make?
- Forgetting that digits are valid characters and skipping them along with punctuation.
- Comparing characters without lowercasing, so “Madam” fails.
- Missing the
left < rightcheck in the skip loops and going out of bounds. - In Rust, computing
len() - 1on an empty string, which underflows ausize. - Using a regex to clean the string and then claiming O(1) space.
Where is this pattern used in the real world?
Valid Palindrome looks like a toy problem, but two pointers shows up anywhere you scan data from both ends or merge two sorted streams. Text editors use it for matching and trimming, databases use a similar idea in merge joins, and DNA tools look for palindromic sequences that mark where proteins bind. Even simple input validation, like checking a mirrored code or trimming whitespace from both ends, follows the same steps.
Which earlier posts in the series should you read?
If you are new here, start with Day 1, Two Sum for the basics. Then read Day 2, Best Time to Buy and Sell Stock, and Day 3, Contains Duplicate. Day 4, Valid Anagram, and Day 5, Group Anagrams, finish the hashing ideas.
Today’s Valid Palindrome post is Day 6 of that run. Want the bigger picture? Our data structures cheat sheet shows where arrays, strings and hash maps fit together.
Frequently asked questions
What is the best approach for Valid Palindrome?
Use two pointers, one at each end of the string. Skip characters that are not letters or digits, compare the rest in lowercase and move inward. It runs in O(n) time and O(1) space.
Is reversing the string an acceptable answer?
Yes, it is correct and runs in O(n) time, but it uses O(n) extra space. Interviewers often ask for the two pointer version as a follow up.
Does an empty string count as a palindrome?
Yes. After cleaning, an empty string reads the same both ways, so the answer is true.
Why does “0P” return false in Valid Palindrome?
Digits are alphanumeric, so 0 is kept and compared with p. They are different characters, so the string is not a palindrome.
What is the two pointer technique?
It is a pattern where two indexes move through data, often from both ends toward the middle, to solve problems in one pass without extra memory.
Conclusion
Valid Palindrome teaches the two pointer habit in its simplest form: one index at each end, skip the noise, compare, move inward. Start with the clean and reverse version, then upgrade to O(1) space once it makes sense. Try the “0P” and empty string cases on your own code before moving on.
Today marks the switch from hashing to two pointers. In the next posts, we will use the same idea on sorted arrays, where the pointers decide which way to move.
