{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Palindrome String – Solution & Complexity

Interview solutions
/
Palindrome String

Solution Walkthrough

  1. Step 1: Understanding the Problem

    • The task is to determine if a given string is a palindrome.
    • Ignore non-alphanumeric characters, and treat upper- and lower-case letters as the same.
    • The goal is to avoid extra storage, so we'll use character-by-character comparison instead of storing a reversed string.

  2. Step 2: Use Two Pointers to Compare Characters

    • Use a two-pointer technique, one starting from the beginning and one from the end of the string.
    • Increment the left pointer and decrement the right pointer after each comparison.
    def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    return left, right

  3. Step 3: Skip Non-Alphanumeric Characters

    • As you move the two pointers, skip any characters that are not alphanumeric (like spaces, punctuation).
    • Use Python's isalnum() method to check if a character is alphanumeric.
    def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        # Skip non-alphanumeric characters
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
    return left, right

  4. Step 4: Compare Characters (Ignore Case)

    • Compare the characters at the left and right pointers, ignoring case.
    • If the characters are not equal, the string is not a palindrome and you can return False immediately.
    def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        # Skip non-alphanumeric characters
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        # Compare characters (ignoring case)
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

  5. Step 5: Return the Result

    • If all characters match as you move the pointers, the string is a palindrome.
    • Once the two pointers meet or cross, return True to indicate the string is a palindrome.
    def is_palindrome(s: str) -> bool:
    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

  6. Step 6: Handle Edge Cases

    • Consider edge cases like an empty string or a string containing only non-alphanumeric characters.
    • These should return True since they can be considered palindromes.
    def is_palindrome(s: str) -> bool:
    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  # Empty strings or strings with only non-alphanumeric characters are palindromes
Learn the Two Pointers pattern: recognition cues, invariant, and ordered practice →

FAQ

See also

Practice Palindrome String online (run code in the browser)Find the Index of the First Occurrence in a String solution (easy)Is Subsequence solution (easy)3Sum solution (medium)3Sum Closest solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?