ToolMight LogoToolMight
EasyTwo PointersPattern: Two Pointers ConvergingPattern: Alphanumeric Filtering

Valid Palindrome

Determine if a string is a palindrome considering only alphanumeric characters and ignoring case. The canonical problem for learning the two-pointer inward convergence technique.

Problem Statement

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Examples & Constraints

Example 1
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: After stripping punctuation and converting to lowercase, "amanaplanacanalpanama" reads identical forwards and backwards.
Example 2
Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome because "raceacar" != "racaecar".
Constraints
  • 1 <= s.length <= 2 * 10^5
  • s consists only of printable ASCII characters.

Two Pointers In-Place (Inward Convergence)

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

Place one pointer at the start and one at the end. Advance past non-alphanumeric characters and compare matching characters inward in O(1) space.

Time ComplexityO(n)

Each character is inspected by at most one pointer. The total number of steps across both pointers is bounded by the string length N.

Space ComplexityO(1)

Operates strictly in-place with two integer pointer variables. No auxiliary strings or buffers are allocated.

Underlying algorithmic logic

The Invariant: Symmetry Across the Center

A palindrome is mirrored across its center. Rather than spending extra memory to create a brand new sanitized string or allocating a reversed copy, we can compare characters directly in-place:

  1. Maintain two pointers: left = 0 and right = s.length - 1.
  2. While left < right:
  • If s[left] is not alphanumeric, advance left++.
  • Else if s[right] is not alphanumeric, decrement right--.
  • Else, compare both characters in lower case:
  • If toLowerCase(s[left]) != toLowerCase(s[right]), the string violates mirror symmetry. Return false immediately!
  • If they match, advance both pointers: left++ and right--.
  1. If the pointers meet or cross without any mismatch, return true.

Why In-Place Two Pointers Outperforms String Reversals

Allocating a filtered string copies up to 200,000 characters into new heap memory. In high-throughput backend services, avoiding temporary allocations reduces garbage collection pauses and prevents memory spikes to O(1) constant auxiliary space.

Step-by-step execution walkthrough

1
Initial Pointers

left points to index 0 ('A'), right points to index 29 ('a'). Both are letters.

left = 'A', right = 'a' -> lowercase match!
2
Skip Punctuation

Advance left past space and comma. Skip right past space.

left skips to 'm', right skips to 'm'
3
Symmetric Match

'm' == 'm'. Both pointers step inward towards center.

left = 3 ('a'), right = 26 ('a')
4
Convergence

All symmetric pairs verified until left >= right.

Symmetry preserved -> return true
Advantages
  • •Optimal O(1) space complexity
  • •Skips punctuation on-the-fly without copying
Trade-offs
  • •Requires boundary guards when advancing inside nested skip loops

Code Implementations

Copy & paste production-ready solutions for Two Pointers In-Place (Inward Convergence) in your language of choice

File: solution.py
Python
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
if __name__ == "__main__":
    test1 = "A man, a plan, a canal: Panama"
    test2 = "race a car"
    print("test1 is palindrome:", is_palindrome(test1))
    print("test2 is palindrome:", is_palindrome(test2))
Interactive visualizer available

Understand Array & Matrix Visually

Explore sequential element access, subsegment manipulations, insertion, deletion, and 2D grid matrix walks. Test live edge cases and watch memory state transitions step-by-step.

Launch Array & Matrix Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
EasyStack
Visualizer

Valid Parentheses

Verify that code brackets (), {}, and [] are properly closed and nested in order. This is the exact algorithm compilers, linters, and IDEs use to detect syntax errors in real-time.

1 approach(O(n))
Learn logic
EasyArrays & Hashing
Visualizer

Two Sum

Find the two numbers in an array that sum up to a target value. The quintessential problem for learning how to trade memory for speed using a Hash Map.

2 approaches(O(n))
Learn logic
MediumTwo Pointers
Visualizer

3Sum

Find all unique triplets in an array that sum up to zero. The premier problem for learning how to combine sorting with two-pointer inward scans to avoid cubic brute force.

1 approach(O(n²))
Learn logic