EasyTwo PointersStringUpdated Sep 2026

125. Valid Palindrome

Asked at Google, Apple

Difficulty

Easy

Time

O(n)

Space

O(1)

Pattern

Two Pointers

Companies

2

Problem

You are given a string s. Decide whether it is a palindrome after you clean it up.

Cleaning means two things: throw away every character that is not a letter or a digit (spaces, commas, colons, punctuation — all gone), and treat uppercase and lowercase letters as the same letter. After that cleanup, the string must read the same forwards and backwards.

Return true if it does, and false if it does not. Note that if nothing is left after cleaning, the empty result counts as a palindrome.

Constraints

  • ●1 <= s.length <= 2 * 10^5
  • ●s contains only printable ASCII characters

Examples

Example 1
Inputs = "A man, a plan, a canal: Panama"
Outputtrue
WhyRemoving spaces, commas and the colon and lowering the case gives "amanaplanacanalpanama". Reading it from either end gives the same letters, so it is a palindrome.
Example 2
Inputs = "race a car"
Outputfalse
WhyAfter cleanup we get "raceacar". The first letter is 'r' and the last is 'r', but the next pair is 'a' and 'c', which differ, so it is not a palindrome.
Example 3
Inputs = " "
Outputtrue
WhyA space is not a letter or digit, so the cleaned string is empty. An empty string reads the same in both directions, so the answer is true.

Asked At

2 companies
CompanyDifficulty
GoogleEasyView all Google questions →
AppleEasyView all Apple questions →

How to Think About It

1

Use two pointers: one at the start, one at the end. Move inward, comparing characters after filtering.

2

Filter: skip non-alphanumeric characters (advance the pointer). Convert to lowercase for case-insensitive comparison.

3

The two pointers approach avoids creating a filtered string. You advance pointers in place, which is O(1) space.

4

Edge cases: empty string (true), single character (true), all non-alphanumeric (true), mixed case.

Optimal Approach

Step 1: Set left = 0, right = len(s) - 1.
Step 2: While left < right:
- Advance left while s[left] is not alphanumeric
- Advance right while s[right] is not alphanumeric
- If s[left].lower() != s[right].lower(), return false
- Move both pointers inward
Step 3: Return true.

The key insight: you don't need to build a filtered string. Just skip non-alphanumeric characters in place.

Time: O(n) — each character is visited at most once. Space: O(1).

Two pointers skip junk and compare

skip while s[left] is not a letter or digitskip while s[right] is not a letter or digitif lower(s[left]) != lower(s[right]) return falseotherwise left += 1, right -= 1
left and right move toward each other, jumping over non-alphanumeric characters, and compare lowercase letters.
ComplexityTime O(n)Space O(1)Each pointer walks over each character at most once, and we compare in place without building a filtered copy of the string.

What Trips People Up in Real Interviews

1

Building a filtered string first. While it works, the two-pointer in-place approach is O(1) space and demonstrates better algorithmic thinking.

2

Forgetting to handle uppercase. Convert both characters to lowercase (or uppercase) before comparing.

3

Not skipping non-alphanumeric characters. The problem says to ignore spaces, punctuation, and special characters.

4

Off-by-one when pointers meet. The loop condition is left < right, not left <= right. When they meet, all pairs have been checked.

5

Not checking bounds in the inner while loops. Always check left < right before advancing to avoid crossing the pointers.

Solution Code

O(n) time
def isPalindrome(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

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Valid Palindrome problem?

Given a string, determine if it is a palindrome considering only alphanumeric characters and ignoring cases. This is a classic two-pointer problem that tests string manipulation and edge case handling.

How do you solve Valid Palindrome?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Valid Palindrome?

Valid Palindrome is asked at Google, Apple. It is a easy difficulty problem.

What are common mistakes on Valid Palindrome?
  • Building a filtered string first. While it works, the two-pointer in-place approach is `O(1)` space and demonstrates better algorithmic thinking.
  • Forgetting to handle uppercase. Convert both characters to lowercase (or uppercase) before comparing.
  • Not skipping non-alphanumeric characters. The problem says to ignore spaces, punctuation, and special characters.
  • Off-by-one when pointers meet. The loop condition is `left < right`, not `left <= right`. When they meet, all pairs have been checked.
  • Not checking bounds in the inner while loops. Always check `left < right` before advancing to avoid crossing the pointers.