Valid Palindrome

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

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):

Watch i and j walk in from both ends, skip the space in place — never building a cleaned buffer — and bail out the moment e and a disagree.

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.