{ }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

    • Return true when s reads the same forwards and backwards after two normalizations: drop every non-alphanumeric character, and compare letters without regard to case.
    • This is not an exact reversal check. For "A man, a plan, a canal: Panama", s == reverse(s) is false because the reversed string is "amanaP :lanac a ,nalp a ,nam A"; the normalized form "amanaplanacanalpanama" is a palindrome.
    • Digits are kept ("12 3 21" normalizes to "12321", so true), and case-folding still has to match letter for letter ("AaB" normalizes to "aab", so false).

  2. Step 2: Filter-and-Reverse vs Two Pointers

    approachhow it workstimeextra space
    Filter + reverseBuild cleaned from the lower-cased alphanumerics, then compare it with a reversed copyO(n)O(n): cleaned plus its reversed copy
    Two pointersWalk inward from both ends of the original s, skipping and comparing in placeO(n)O(1)

    Filter + reverse is a fine first answer, for example in Python cleaned = [c.lower() for c in s if c.isalnum()] followed by return cleaned == cleaned[::-1]. The two-pointer scan answers the follow-up: it never builds a copy, and it can stop at the first mismatch instead of normalizing the whole string first.

  3. Step 3: 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

  4. Step 4: Skip Non-Alphanumeric Characters

    • As you move the two pointers, skip any characters that are not alphanumeric (like spaces, punctuation).
    • The left < right guard in each inner loop keeps a pointer from running past the other.
    • The constraints define alphanumeric as ASCII A-Z, a-z, 0-9. The JavaScript, Go, Rust, Ruby, and C++ (std::isalnum in the default "C" locale) checks are ASCII-only. Python's str.isalnum() and Java's Character.isLetterOrDigit() also accept non-ASCII letters and digits such as é, so all versions agree on valid inputs but are not interchangeable for arbitrary Unicode text.
    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

  5. Step 5: 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.
    • Otherwise move both pointers inward. Once they meet or cross, every pair has matched, so return True.
    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

  6. Step 6: Dry run / state trace

    Trace s = "A man, a plan, a canal: Panama" (length 30). Indices are positions in the original string; nothing is copied.

    #left (index char)right (index char)what happens
    10 A29 aA vs a match after lower-casing
    2skip 1 ' ', stop at 2 m28 mmatch
    3–43 a, 4 n27 a, 26 ntwo direct matches
    5skip 5 , and 6 ' ', stop at 7 a25 amatch
    6skip 8 ' ', stop at 9 p24 Pp vs P matches only because case is ignored
    710 lskip 23 ' ' and 22 :, stop at 21 lmatch
    8–911 a, 12 n20 a, 19 ntwo direct matches
    10skip 13 , and 14 ' ', stop at 15 a18 amatch
    11skip 16 ' ', stop at 17 c17 cpointers meet on the middle c; comparing it with itself is harmless

    After row 11, left = 18 and right = 16, so the loop ends and the function returns True: 11 comparisons, 9 skipped characters, O(1) extra space.

  7. Step 7: Failing Example: Early Exit

    Trace s = "race a car" (length 10).

    leftrightwhat happens
    0 r9 rmatch
    1 a8 amatch
    2 c7 cmatch
    3 eskip 6 ' ', stop at 5 ae ≠ a: return False immediately

    Index 4 is never examined. Filter + reverse would first normalize all 10 characters to "raceacar" and then find the same mismatch against "racaecar".

  8. Step 8: Handle Edge Cases

    • Empty string: right starts at -1, so left < right is false immediately and the function returns True.
    • Only punctuation, e.g. "...!!!": the left skip loop advances until left == right (index 5), comparing that ! with itself passes, the pointers cross, and the result is True. The normalized string is empty, and an empty string reads the same in both directions.
    • Single character: left == right from the start, so the loop never runs and the result is True.
    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