Big O Practice: Valid Palindrome

def is_palindrome(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

Variables

• n - length of the input string

Explanation

The two pointers together cover each character at most once - **O(n)** total. Only two indices are tracked, so space is **O(1)**. The nested skip-loops can fool you into thinking it is quadratic, but the inner work is amortized over the outer.

More Big O practice problems · Today's daily problem