What is the time and space complexity of Valid Palindrome?

The optimal solution runs in O(n) time and O(1) space.

← All problems

Two PointersEasy

Next: Valid ParenthesesNext →

Valid Palindrome

Two PointersEasy

Step 1 of 8 · Understand

1. Understand the problem

Problem statement

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Given a string s, return true if it is a palindrome, or false otherwise.

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

Problem statement

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.

Quick check

Before any hints, take a guess.

"A man, a plan, a canal: Panama" is a palindrome. After removing spaces and punctuation, it reads the same forwards and backwards. How do you check that without reversing the whole string?

Pick an answer to continue

2. Spot the pattern

Before any code, every problem starts with a question. For this problem:

“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.

Why not Reverse and compare?

You could filter the string, reverse it, and compare, but that costs O(n) extra space. Two pointers compare from both ends inward, skipping non-alphanumerics, in O(1) space.

3. 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)

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.

Quick check

You're checking "racecar" (7 characters). The pointers have been moving inward without a mismatch. Now left = 3 and right = 3, both on the middle 'e'. What happens next?

Pick an answer to continue

8. Review & common mistakes

Lock it in

What is the signal that tells you to use the Two Pointers pattern? Write it in one sentence, in your own words.

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.

Pattern family

Valid Palindrome

1. Understand the problem

1. Understand the problem

Quick check

2. Spot the pattern

Quick check

3. Brute force idea

4. Climb the hint ladder

5. The optimized approach

6. Dry run, row by row

Quick check

7. The code

8. Review & common mistakes