DSA Valid Palindrome

The problem

A palindrome reads the same forwards and backwards. The Valid Palindrome problem asks whether a phrase is a palindrome after cleaning. Cleaning keeps only letters and digits and lowercases every letter.

Spaces and punctuation do not count. Case does not count. Every kept character counts, including digits.

cases = [
    ('A man, a plan, a canal: Panama', True),
    ('race a car', False),
    ('No lemon, no melon', True),
    ('0P', False),
    ('', True),
]
for phrase, expected in cases:
    print(repr(phrase), '->', expected)

Intuition

The first idea compares the raw phrase with its reverse. That test fails on real phrases. Spaces, commas and capital letters differ even when the letters match.

phrase = 'No lemon, no melon'
print('phrase:', phrase)
print('reversed:', phrase[::-1])
print('raw test:', phrase == phrase[::-1])
print('cleaned phrase:', 'nolemonnomelon')

Cleaning is therefore part of the problem, not a detail. The cleaned text decides the answer. The raw text only supplies the characters.

Brute force

The straightforward method cleans the phrase into a new string. It then builds the reverse of that string. Equal strings mean a palindrome.

def is_palindrome_brute(text):
    clean = ''
    for ch in text:
        if ch.isalnum():
            clean += ch.lower()
    reversed_clean = ''
    for ch in clean:
        reversed_clean = ch + reversed_clean
    return clean == reversed_clean, clean

for phrase in ['A man, a plan, a canal: Panama', 'race a car', 'No lemon, no melon']:
    verdict, clean = is_palindrome_brute(phrase)
    print(repr(phrase), 'clean:', clean, '->', verdict)

The method builds two extra strings. Each prepend in the reverse also copies the string built so far. A comparison from both ends needs no copies at all.

The optimal solution: pointers that skip and compare

The key idea is two pointers on the original phrase. Each pointer skips characters that cleaning would drop, then the kept pair is compared in lowercase.

def is_palindrome(text):
    left = 0
    right = len(text) - 1
    while left < right:
        while left < right and not text[left].isalnum():
            left += 1
        while left < right and not text[right].isalnum():
            right -= 1
        if text[left].lower() != text[right].lower():
            return False
        left += 1
        right -= 1
    return True

cases = ['A man, a plan, a canal: Panama', 'race a car', 'No lemon, no melon', '0P', '']
for phrase in cases:
    print(repr(phrase), '->', is_palindrome(phrase))

Walkthrough

Take the phrase 'race a car'. Its cleaned form is 'raceacar'. The pointers below work on the cleaned form so each pair is visible.

s = 'raceacar'
left = 0
right = len(s) - 1
while left < right:
    print('compare', s[left], 'with', s[right], ':', s[left] == s[right])
    if s[left] != s[right]:
        print('mismatch, the answer is False')
        break
    left += 1
    right -= 1

Three pairs match. The fourth pair compares e with a. That one mismatch settles the answer, and the middle is never reached.

Complexity

Time is O(n). Each pointer moves inward only, so each character is visited a small fixed number of times.

Space is O(1) for the pointer version. No cleaned copy and no reversed copy are built.

def brute_copies(text):
    clean = ''
    copies = 0
    for ch in text:
        if ch.isalnum():
            clean += ch.lower()
            copies += len(clean)
    return copies

def pointer_visits(text):
    left = 0
    right = len(text) - 1
    visits = 0
    while left < right:
        visits += 1
        if text[left].lower() != text[right].lower():
            break
        left += 1
        right -= 1
    return visits

for text in ['abba', 'racecar', 'nolemonnomelon']:
    print(text, 'brute copies:', brute_copies(text), 'pointer pair visits:', pointer_visits(text))

Edge cases and pitfalls

An empty phrase is a palindrome. A phrase with no letters or digits cleans to empty, so it also answers True. The pointers meet at once in both cases.

Digits are kept characters. The phrase '0P' cleans to '0p', and 0 differs from p. Dropping digits during cleaning would flip that answer, which is the pitfall the run below exposes.

def is_palindrome(text):
    left = 0
    right = len(text) - 1
    while left < right:
        while left < right and not text[left].isalnum():
            left += 1
        while left < right and not text[right].isalnum():
            right -= 1
        if text[left].lower() != text[right].lower():
            return False
        left += 1
        right -= 1
    return True

print('empty:', is_palindrome(''))
print('single letter:', is_palindrome('a'))
print('only punctuation:', is_palindrome('.,!'))
print('digits count:', is_palindrome('0P'))
print('mixed case:', is_palindrome('RaceCar'))