DSAPrep
EasyTwo Pointers

Valid Palindrome

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: s is an empty string "" after removing non-alphanumeric characters. Since an empty string reads the same forward and backward, it is a palindrome.

Constraints

  • 1 <= s.length <= 2 * 10^5
  • s consists only of printable ASCII characters.
View original on LeetCode ↗

The naive approach builds a cleaned copy of the string and compares it to its reverse. The optimal approach never builds a copy at all: walk in from both ends of the original string at once, skip characters that don’t count, and bail out the instant two letters disagree.

Build & Reverse

Time O(n)Space O(n)

Strip out every non-alphanumeric character, lowercase what’s left, and check whether the result reads the same backward. This is correct because it directly implements the definition of a cleaned palindrome — but it pays for a second full copy of the string (the cleaned list) and another reversed copy just to compare.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        cleaned = [c.lower() for c in s if c.isalnum()]
        return cleaned == cleaned[::-1]

Complexity: building the cleaned list is O(n), and comparing it to its reverse is another O(n) — so O(n) time overall, but it needs O(n) extra space for the cleaned list (and another O(n) for the reversed copy).

Two Pointers (One Pass)

OptimalTime O(n)Space O(1)

Keep a pointer i at the start and j at the end of the original string. Advance i forward and j backward past any character that isn’t alphanumeric — those characters are irrelevant to the check and never need to live in a separate buffer. Once both pointers land on real characters, compare them case-insensitively; any mismatch means the phrase isn’t a palindrome. If the pointers cross without a mismatch, every pair matched, so it is one.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        i, j = 0, len(s) - 1
        while i < j:
            while i < j and not s[i].isalnum():
                i += 1
            while i < j and not s[j].isalnum():
                j -= 1
            if s[i].lower() != s[j].lower():
                return False
            i += 1
            j -= 1
        return True

Tracing s = "race a car" (expected false):

i
r
0
a
1
c
2
e
3
4
a
5
6
c
7
a
8
j
r
9
i = 0j = 9
1 / 5
comparingcurrentdiscarded

s[0]='r', s[9]='r' → match. Move both pointers inward.

Correctness: the inner while loops only ever skip characters that isalnum() rejects — they don’t change which alphanumeric characters get compared, so this checks exactly the same pairs the cleaned-string version would, just without materializing the cleaned string. The moment a pair disagrees, the phrase can’t be a palindrome, so returning False immediately is safe.

Complexity: each of i and j moves strictly toward the other and the loop stops when they meet, so every character is visited at most once → O(n) time. No auxiliary buffer is allocated — only two integer pointers — so it’s O(1) space, which the two-pass version can’t claim.