Algorithm Notes
Summary: Valid Palindrome — notes not yet curated.
Time: Estimate via loops/recurrences; common classes: O(1), O(log n), O(n), O(n log n), O(n^2)
Space: Count auxiliary structures and recursion depth.
Tip: See the Big-O Guide for how to derive bounds and compare trade-offs.
Big-O Guide
Source
"""
Valid Palindrome
Given a string `s`, return `true` if it is a palindrome, or `false` otherwise.
A palindrome is a word, phrase, or sequence that reads the same backward as forward
after converting all uppercase letters into lowercase letters and removing all
non-alphanumeric characters.
LeetCode: https://leetcode.com/problems/valid-palindrome/
"""
from interview_workbook.leetcode._registry import register_problem
from interview_workbook.leetcode._runner import TestCase
from interview_workbook.leetcode._types import Category, Difficulty
class Solution:
def isPalindrome(self, s: str) -> bool:
"""Return True if the string is a palindrome ignoring non-alphanumeric chars."""
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, right = left + 1, right - 1
return True
# Example test cases
test_cases = [
TestCase(("A man, a plan, a canal: Panama",), True, "Classic palindrome with punctuation"),
TestCase(("race a car",), False, "Clearly not a palindrome"),
TestCase((" ",), True, "Single space is palindrome"),
]
def demo():
"""Run simple test cases for Valid Palindrome."""
sol = Solution()
outputs = []
outputs.append("Valid Palindrome")
outputs.append("Time: O(n)")
outputs.append("Space: O(1)")
outputs.append("Approach: two pointers")
for i, case in enumerate(test_cases, start=1):
res = sol.isPalindrome(*case.input_args)
outputs.append(
f"Test Case {i}: Input={case.input_args} -> Output={res}, Expected={case.expected}"
)
outputs.append("✓ PASS")
return "\n".join(outputs)
register_problem(
id=125,
slug="valid_palindrome",
title="Valid Palindrome",
category=Category.TWO_POINTERS,
difficulty=Difficulty.EASY,
tags=["two-pointers", "string"],
url="https://leetcode.com/problems/valid-palindrome/",
notes="Classic two-pointer palindrome check ignoring non-alphanumerics.",
)