Two PointersEasy

Valid Palindrome

Two PointersEasy

Step 1 of 8 · Understand

1. Understand the problem

A phrase is a palindrome if, after removing everything that isn't a letter or digit and ignoring case, it reads the same forward and backward. Given a string, return whether it's a palindrome.

Input

A string `s` that may contain letters, digits, spaces, and punctuation.

Output

A boolean — `true` if the cleaned string is the same forwards and backwards, `false` otherwise.

Examples

input → s = "A man, a plan, a canal: Panama"

output → true

After stripping non-alphanumeric chars and lowercasing: "amanaplanacanalpanama" — a palindrome.

input → s = "race a car"

output → false

Cleaned: "raceacar" — not the same forwards and backwards.

input → s = " "

output → true

Empty after cleaning — an empty string is a palindrome.

1. Understand the problem

A phrase is a palindrome if, after removing everything that isn't a letter or digit and ignoring case, it reads the same forward and backward. Given a string, return whether it's a palindrome.

Input

A string `s` that may contain letters, digits, spaces, and punctuation.

Output

A boolean — `true` if the cleaned string is the same forwards and backwards, `false` otherwise.

Examples

input → s = "A man, a plan, a canal: Panama"

output → true

After stripping non-alphanumeric chars and lowercasing: "amanaplanacanalpanama" — a palindrome.

input → s = "race a car"

output → false

Cleaned: "raceacar" — not the same forwards and backwards.

input → s = " "

output → true

Empty after cleaning — an empty string is a palindrome.

2. Brute force idea

Filter the string down to only alphanumeric characters and lowercase everything. Then reverse that cleaned string and check if it equals the original cleaned string.

Brute force — the slow one

O(n)

cleaned = [c.lower() for c in s if c.isalnum()]
# cleaned is e.g. ['a','m','a','n',...]

return cleaned == cleaned[::-1]    # ← reverse and compare

Why this is too slow

This approach is O(n) time and O(n) space because you're building the full cleaned list in memory, then building a second reversed copy to compare. It works, but you can do the check without allocating that extra space.

Why this is not ideal for interviews

The filter-and-reverse trick solves the problem, but it allocates O(n) extra space. Interviewers for roles where memory matters will want you to recognize the two-pointer pattern — checking from both ends simultaneously with no extra array required.

Time: O(n)

Space: O(n)

3. Spot the pattern

Before any code, every problem starts with a question. For the Two Pointers pattern, that question is:

“Can I check this from both ends at once, skipping non-alphanumeric characters as I go?”

Palindrome checks are the textbook two-pointer problem. When you need to compare a string against its mirror image, start one pointer at each end and walk them toward the middle — you never need to build a reversed copy.

5. The optimized approach

Use two pointers starting at opposite ends of the string. Skip non-alphanumeric characters on each side, then compare the characters the pointers land on. If any pair mismatches, return false. When the pointers meet in the middle, return true.

Pseudocode

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

6. Dry run, row by row

Trace it with the first example — s = "A man, a plan, a canal: Panama".

step	left	right	s[left]	s[right]	match?
1	0	30	A → a	a	yes
2	1	28	m	m	yes
3	3	26	a	a	yes
4	5	24	n	n	yes
5	…	…	…	…	yes

step 1: "A man, a plan, a canal: Panama" — left skips to A (index 0), right skips to a (index 30).

step 2: Both pointers move inward, skipping spaces and punctuation.

step 3: Continuing inward.

step 4: Still matching.

step 5: All pairs match. left >= right — return true.

8. Review & common mistakes

Common mistakes

Forgetting to skip non-alphanumeric characters
The input can have spaces, commas, colons — comparing those directly will give wrong answers. Both pointers need their own inner loop to skip past any character that isn't a letter or digit.
Comparing without lowercasing
'A' and 'a' are the same character for palindrome purposes. Always compare with `.toLowerCase()` / `.lower()` so case doesn't break your check.
Building the reversed string anyway
It's tempting to filter into an array and reverse it. That works but uses O(n) space. The two-pointer approach is O(1) space — worth knowing when the interviewer asks about memory.

Try next (when these problems ship)

Valid Anagram
Move Zeroes

Ready to go deeper?

Unlock 10 more problems covering Sliding Window, Binary Search, Linked Lists, Trees, and more — same guided format, same hint ladder, one-time $10.

See all problems →

Write your solution above and hit Run tests. Results and tips appear here.

Valid Palindrome

1. Understand the problem

1. Understand the problem

2. Brute force idea

3. Spot the pattern

4. Climb the hint ladder

5. The optimized approach

6. Dry run, row by row

7. The code

8. Review & common mistakes