Valid Palindrome
An easy Strings interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Strings
- Sheets
- 2
- Core for
- 14 roles
The problem
Determine whether a given string is a palindrome after converting all uppercase letters to lowercase and removing all non-alphanumeric characters.
Example 1
- Input
- s="Was it a car or a cat I saw?"
- Output
- true
- Why
- Keeping only letters and digits in lower case gives "wasitacaroracatisaw", which reads the same backwards.
Example 2
- Input
- s="code, edoc x"
- Output
- false
- Why
- Cleaned up it becomes "codeedocx", while its reverse is "xcodeedoc", so the two do not match.
Example 3
- Input
- s=" "
- Output
- true
- Why
- Stripping all whitespace leaves an empty string, which qualifies as a palindrome.
Constraints
- 1 <= s.length <= 2 * 10^5
- s consists only of printable ASCII characters
How to think about it
Updated 2026-09-29Building a cleaned copy of the string costs an unnecessary full allocation and extra traversal. Positioning pointers at both ends and advancing inward past non-alphanumeric characters lets comparisons happen strictly in place, terminating the instant an asymmetric alphanumeric mismatch is found.
Approaches, worst first
Filter string and check reverse
time O(n) · space O(n)
Extract all alphanumeric characters into a fresh lowercase string or buffer, then compare that buffer to its reversed copy. Correct and concise, but it allocates heap memory for two auxiliary strings of up to input length.
Two pointers in placeWrite this one
time O(n) · space O(1)
Maintain left and right pointers at both extremities. While left < right, skip non-alphanumeric characters on both flanks, compare the remaining characters case-insensitively, and increment left while decrementing right. Halts immediately upon any character inequality.
Where people lose marks · 3
- Neglecting numeric digits: digits like '0' through '9' are alphanumeric and must match each other, unlike punctuation marks which must be skipped entirely.
- Character case conversion collision: non-alphabetic ASCII characters shifted naively by bit masks or arithmetic might collide with lowercase letters; verify alphanumeric status before converting.
- Skipping pointers running past bounds: while skipping invalid characters inside inner loops, left and right pointers must still respect the invariant left < right.
The theory behind it
Strings — the ground this problem stands on. All Strings problems
What Strings is
A string is an ordered necklace of text characters, like letters printed along a ribbon of paper. Each character sits at an exact numeric slot, holding a glyph such as a letter, punctuation mark, or digit. In many programming languages, ribbons cannot be edited after creation, meaning changing a single character requires pressing an entirely new ribbon from scratch.
When to reach for it
Reach for string techniques when inputs consist of words, DNA sequences, serialized data formats, or sentences. Clues include questions testing palindromes, anagram matches, substring patterns, parenthesis balancing, or character frequency counts. Whenever an algorithm asks to transform capitalization, parse structured tokens, or compute edits between two phrases, string representations are the core subject.
How the pattern works
Think of characters as small integer codes ranging across standard character sets. Frequency tables with fixed sizes often replace heavy hash maps when tallying occurrences. For search tasks, maintain rolling state using character indices or sliding borders. When building output text through repeated appends, accumulate pieces inside a mutable list or string builder rather than concatenating strings directly, avoiding quadratic copy overhead.
More Strings problems
Target Roles
Core requirement for 14 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .