#125 Valid Palindrome
the problem
In plain words
After lowercasing and removing everything that isn't a letter or digit, does the string read the same forwards and backwards?
in s = "A man, a plan, a canal: Panama"
out true
"amanaplanacanalpanama" is a palindrome.
in s = "race a car"
out false
- 1 ≤ s.length ≤ 2·10⁵
- Printable ASCII characters
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternTwo pointers (opposite ends)
A palindrome is a mirror: compare the first and last valid characters, then move both inwards. No need to build a cleaned copy.
solutions
From brute force to optimal
Build a cleaned lowercase copy, reverse it, check equality.
- Append each letter/digit (lowercased) to a StringBuilder.
- Compare the string with its reverse.
One pass to clean, one to reverse, one to compare.
The cleaned copy and its reverse.
class Solution { public boolean isPalindrome(String s) { StringBuilder clean = new StringBuilder(); for (char c : s.toCharArray()) { if (Character.isLetterOrDigit(c)) clean.append(Character.toLowerCase(c)); } String forward = clean.toString(); String backward = clean.reverse().toString(); return forward.equals(backward); }}Compare mirrored characters directly in the original string, skipping non-alphanumerics.
- left = 0, right = n−1.
- Skip non-alphanumeric characters on each side.
- If lowercase characters differ → false; otherwise move both inwards.
Each character is visited at most once by one pointer.
Only two indices.
class Solution { public boolean isPalindrome(String s) { int left = 0, right = s.length() - 1; while (left < right) { // skip anything that is not a letter or digit 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; }}Dry run
in the room
How to say it in the interview
talk track
- Clarify: are digits included? Is the empty string a palindrome? (Yes and yes.)
- Mention the brute force in one line, then say you can do O(1) space with two pointers.
- Point out the inner
left < rightguard that prevents running off the ends on inputs like ".,".
traps
- Forgetting the
left < rightcheck inside the skip loops. - Comparing without lowercasing ('A' vs 'a').
what they ask next
Follow-ups
Valid Palindrome II (LC 680): may delete at most one character?
On the first mismatch, try skipping either the left or the right character and check the rest with the same two-pointer routine — still O(n).
before you submit
Edge cases to test
- Only spaces or punctuation (" " or ".,"): nothing to compare, so it is a palindrome → true.
- Digits count as characters: "0P" → false, because '0' ≠ 'p'.
- Mixed case: "Aa" → true after lowercasing.
- 2·10⁵ characters: the cleaned-copy version works but allocates O(n) memory; two pointers needs none.
practise next
Similar problems
- #344Reverse StringEasyin Recursion
- #9Palindrome NumberEasyin Math & Numbers
- #5Longest Palindromic SubstringMediumin Dynamic Programming