EasyBlind75StringTwo Pointers

Valid Palindrome

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.

Examples

Input
s = 'A man, a plan, a canal: Panama'
Output
true

'amanaplanacanalpanama' is a palindrome.

Input
s = 'race a car'
Output
false

'raceacar' is not a palindrome.

Constraints

  • •1 <= s.length <= 2 * 10^5
  • •s consists only of printable ASCII characters.

Approaches

Clean the string and compare it with its reverse.

CodeT: O(n) | S: O(n)
def is_palindrome(s):
    cleaned = ''.join(c.lower() for c in s if c.isalnum())
    return cleaned == cleaned[::-1]

Use two pointers from both ends, skipping non-alphanumeric characters.

CodeT: O(n) | S: O(1)
def is_palindrome(s):
    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

Same logic as two pointers but implemented recursively.

Diagram

s = 'A man, a plan, a canal: Panama' Skip spaces and punctuation, compare chars All match -> True
CodeT: O(n) | S: O(n)
def is_palindrome(s):
    def check(left, right):
        if left >= right:
            return True
        if not s[left].isalnum():
            return check(left + 1, right)
        if not s[right].isalnum():
            return check(left, right - 1)
        if s[left].lower() != s[right].lower():
            return False
        return check(left + 1, right - 1)
    return check(0, len(s) - 1)

Complexity Comparison

String Reversal
T: O(n)S: O(n)

Clean the string and compare it with its reverse.

Two Pointers
T: O(n)S: O(1)

Use two pointers from both ends, skipping non-alphanumeric characters.

Two Pointers - Recursive
T: O(n)S: O(n)

Same logic as two pointers but implemented recursively.

Common Mistakes

Forgetting to convert to lowercase before comparing

Not skipping non-alphanumeric characters properly

Using extra space when O(1) solution is possible

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems