How do you approach Valid Palindrome?

You could build a cleaned string and compare it to its reverse - but can you do it without extra space?

What is the time complexity of Valid Palindrome?

Time complexity: O(n) - each character is visited at most once. Space complexity: O(1) - no extra string is built.

What are common mistakes on Valid Palindrome?

Forgetting the input has to be sorted. If it is not, the pointer moves mean nothing and the answer only looks right on the sample. Moving both pointers on a match when only one should move, which steps over valid pairs. Choosing left < right where left <= right is meant. The first never examines the middle element.

gitGood.dev

← Back to problems

Valid Palindrome

EasyAlgorithms

Description

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. Alphanumeric characters include letters and numbers. Given a string `s`, return `true` if it is a palindrome, or `false` otherwise.

Example 1

Input: s = "A man, a plan, a canal: Panama"

Output: true

Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2

Input: s = "race a car"

Output: false

Explanation: "raceacar" is not a palindrome.

Example 3

Input: s = " "

Output: true

Explanation: After removing non-alphanumeric characters, s is an empty string, which reads the same forward and backward.

Constraints

- 1 <= s.length <= 2 * 10^5 - s consists only of printable ASCII characters.

Valid Palindrome: approach, complexity and pitfalls

An easy two pointers problem, graded against 7 test cases (4 of them hidden).

The pattern: Two Pointers

Two indices walking a sorted array or string, usually from opposite ends.

Reach for it when you see: A sorted input, a palindrome check, or a pair/triplet that must satisfy a condition.

More Two Pointersproblems →

If you are stuck

Show the 3-step hint ladder

You could build a cleaned string and compare it to its reverse - but can you do it without extra space?
Use two pointers, one starting at each end of the string.
Advance each pointer past non-alphanumeric characters, then compare the lowercased characters before moving both inward.

The optimal approach

Show the approach: Two Pointers

Place one pointer at each end of the string. Skip any character that is not a letter or digit. When both pointers rest on alphanumeric characters, compare them case-insensitively - if they differ, the string is not a palindrome. Move both pointers inward and repeat until they cross.

Time: O(n) - each character is visited at most once
Space: O(1) - no extra string is built

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Two Pointers mistakes

These apply to the pattern as a whole, not just this problem.

Forgetting the input has to be sorted. If it is not, the pointer moves mean nothing and the answer only looks right on the sample.
Moving both pointers on a match when only one should move, which steps over valid pairs.
Choosing `left < right` where `left <= right` is meant. The first never examines the middle element.

← Back to problems

Valid Palindrome

EasyAlgorithms

Description

Example 1

Input: s = "A man, a plan, a canal: Panama"

Output: true

Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2

Input: s = "race a car"

Output: false

Explanation: "raceacar" is not a palindrome.

Example 3

Input: s = " "

Output: true

Explanation: After removing non-alphanumeric characters, s is an empty string, which reads the same forward and backward.

Constraints

- 1 <= s.length <= 2 * 10^5 - s consists only of printable ASCII characters.

Valid Palindrome: approach, complexity and pitfalls

An easy two pointers problem, graded against 7 test cases (4 of them hidden).

The pattern: Two Pointers

Two indices walking a sorted array or string, usually from opposite ends.

Reach for it when you see: A sorted input, a palindrome check, or a pair/triplet that must satisfy a condition.

More Two Pointersproblems →

If you are stuck

Show the 3-step hint ladder

You could build a cleaned string and compare it to its reverse - but can you do it without extra space?
Use two pointers, one starting at each end of the string.
Advance each pointer past non-alphanumeric characters, then compare the lowercased characters before moving both inward.

The optimal approach

Show the approach: Two Pointers

Time: O(n) - each character is visited at most once
Space: O(1) - no extra string is built

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Two Pointers mistakes

These apply to the pattern as a whole, not just this problem.

Forgetting the input has to be sorted. If it is not, the pointer moves mean nothing and the answer only looks right on the sample.
Moving both pointers on a match when only one should move, which steps over valid pairs.
Choosing `left < right` where `left <= right` is meant. The first never examines the middle element.