Valid Palindrome

Problem

Given a string, determine if it is a palindrome considering only alphanumeric characters and ignoring case.

Approach

Two pointers from both ends. Skip non-alphanumeric characters. Compare lowercase characters at each pointer position.

When to Use

String validity checks, symmetry problems. Foundation for palindrome family (longest palindromic substring, palindrome partitioning).

Complexity

Time	O(n)
Space	O(1)

Implementation

SolutionTestsChallenge

valid_palindrome

Valid Palindrome — check if string is a palindrome ignoring non-alnum and case.

Problem

Given a string, determine if it is a palindrome considering only alphanumeric characters and ignoring case.

Approach

Two pointers from both ends. Skip non-alphanumeric characters. Compare lowercase characters at each pointer position.

When to use

String validity checks, symmetry problems. Foundation for palindrome family (longest palindromic substring, palindrome partitioning).

Complexity

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

is_palindrome

is_palindrome(s: str) -> bool

Return True if s is a palindrome (alphanumeric only, case-insensitive).

is_palindrome("A man, a plan, a canal: Panama") True is_palindrome("race a car") False

Source code in src/algo/strings/valid_palindrome.py

def is_palindrome(s: str) -> bool:
    """Return True if *s* is a palindrome (alphanumeric only, case-insensitive).

    >>> is_palindrome("A man, a plan, a canal: Panama")
    True
    >>> is_palindrome("race a car")
    False
    """
    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

tests/strings/test_valid_palindrome.py

"""Tests for the valid palindrome problem."""

from hypothesis import given
from hypothesis import strategies as st

from algo.strings.valid_palindrome import is_palindrome


class TestIsPalindrome:
    def test_basic_palindrome(self) -> None:
        assert is_palindrome("A man, a plan, a canal: Panama")

    def test_not_palindrome(self) -> None:
        assert not is_palindrome("race a car")

    def test_empty_string(self) -> None:
        assert is_palindrome("")

    def test_single_character(self) -> None:
        assert is_palindrome("a")

    def test_only_non_alnum(self) -> None:
        assert is_palindrome(",.!?@#")

    def test_numeric_palindrome(self) -> None:
        assert is_palindrome("12321")

    @given(
        s=st.text(
            alphabet=st.characters(categories=("L", "N")), min_size=1, max_size=30
        )
    )
    def test_doubled_string_is_palindrome(self, s: str) -> None:
        # s + reverse(s) is always a palindrome
        assert is_palindrome(s + s[::-1])

Implement it yourself

Run: just challenge strings valid_palindrome

Then implement the functions to make all tests pass. Use just study strings for watch mode.

Reveal Solution

valid_palindrome

Valid Palindrome — check if string is a palindrome ignoring non-alnum and case.

Problem

Given a string, determine if it is a palindrome considering only alphanumeric characters and ignoring case.

Approach

Two pointers from both ends. Skip non-alphanumeric characters. Compare lowercase characters at each pointer position.

When to use

String validity checks, symmetry problems. Foundation for palindrome family (longest palindromic substring, palindrome partitioning).

Complexity

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

is_palindrome

is_palindrome(s: str) -> bool

Return True if s is a palindrome (alphanumeric only, case-insensitive).

is_palindrome("A man, a plan, a canal: Panama") True is_palindrome("race a car") False

Source code in src/algo/strings/valid_palindrome.py

def is_palindrome(s: str) -> bool:
    """Return True if *s* is a palindrome (alphanumeric only, case-insensitive).

    >>> is_palindrome("A man, a plan, a canal: Panama")
    True
    >>> is_palindrome("race a car")
    False
    """
    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