Valid Palindrome

Medium · rating 1050 · strings, two-pointers

Read a line. Considering only alphanumeric characters and ignoring case, print YES if it reads the same forwards and backwards, otherwise NO.

Editorial

Approach

Use two pointers, one at each end. Skip any non-alphanumeric characters, compare the two characters case-insensitively, then move both inward. If any pair differs, it's not a palindrome; if the pointers cross, it is.

Why two pointers

A palindrome reads the same forwards and backwards, so the k-th character from the front must equal the k-th from the back. Comparing from both ends toward the middle checks exactly those constraints in a single O(n) pass with no extra string allocations.

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, j = i + 1, j - 1
return True

Complexity

Time: O(n). Space: O(1).

Open Valid Palindrome in Code Arena →