Palindrome

Description

Given a string s, return true if it is a palindrome (reads the same forward and backward), or false otherwise. Consider only alphanumeric characters and ignore case.

Example 1:
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: After removing non-alphanumeric and lowercasing: "amanaplanacanalpanama" is a palindrome.

Example 2:
Input: s = "race a car"
Output: false
Explanation: After processing: "raceacar" is not a palindrome.

Example 3:
Input: s = " "
Output: true
Explanation: After removing non-alphanumeric: "" (empty string) is a palindrome.

Constraints

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

Signature

def solution(s: str) -> bool: ...

Complexity

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

Hints

Pattern: Use two pointers: one at the start, one at the end
Approach: Move pointers inward, skipping non-alphanumeric chars. Compare lowercase versions.
Complexity: You only need to traverse the string once - O(n) time, O(1) space

Solutions

Haskell

module Solution (solution) where

import qualified Data.Text as T

solution :: T.Text -> Bool
solution t = go 0 (T.length t - 1)
  where
    go l r
      | l >= r = True
      | T.index t l /= T.index t r = False
      | otherwise = go (l + 1) (r - 1)

#include <stdbool.h>
#include <string.h>

bool solution(char *s) {
  int len = strlen(s);
  if (len == 0)
    return true;

  int start = 0;
  int end = len - 1;

  while (start < end) {
    if (s[start] != s[end]) {
      return false;
    }
    start++;
    end--;
  }

  return true;
}

C++

#include <string>
using namespace std;

bool solution(string s) {
  int left = 0;
  int right = s.length() - 1;
  while (left < right) {
    if (s[left] != s[right])
      return false;
    left++;
    right--;
  }
  return true;
}

Python

def solution(s):
    if len(s) == 0:
        return True

    start = 0
    end = len(s) - 1

    while start < end:
        if s[start] != s[end]:
            return False

        start += 1
        end -= 1

    return True

Rust

pub fn solution(s: &str) -> bool {
    let mut chars = s.chars();
    while let (Some(front), Some(back)) = (chars.next(), chars.next_back()) {
        if front != back {
            return false;
        }
    }
    true
}