Coding problem · Easy · Two Pointers

Valid Palindrome

Easy Algorithms & data structures Seen at Meta, Microsoft, Spotify

A phrase is a palindrome if, after converting letters to lowercase and removing all non-alphanumeric characters, it reads the same forward and backward. Given a string s, return true if it is a palindrome.

Example 1

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

Example 2

Input: s = "race a car"
Output: false

Constraints

s is ASCII

Hints

Hint 1

Use one pointer at each end; skip characters that aren't letters or digits.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(1)

Move left and right towards each other, skipping non-alphanumeric characters and comparing lowercase letters. O(1) extra space versus building a cleaned copy.

Reference solution

function isPalindrome(s) {
  const ok = (c) => /[a-z0-9]/i.test(c);
  let i = 0, j = s.length - 1;
  while (i < j) {
    if (!ok(s[i])) i++;
    else if (!ok(s[j])) j--;
    else if (s[i++].toLowerCase() !== s[j--].toLowerCase()) return false;
  }
  return true;
}

function isPalindrome(s: string): boolean {
  const clean = s.toLowerCase().replace(/[^a-z0-9]/g, "");
  return clean === [...clean].reverse().join("");
}

def is_palindrome(s: str) -> bool:
    i, j = 0, len(s) - 1
    while i < j:
        if not s[i].isalnum():
            i += 1
        elif not s[j].isalnum():
            j -= 1
        elif s[i].lower() != s[j].lower():
            return False
        else:
            i, j = i + 1, j - 1
    return True

<?php

function isPalindrome(string $s): bool
{
    $clean = preg_replace('/[^a-z0-9]/', '', strtolower($s));
    return $clean === strrev($clean);
}

class Solution {
    public boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            char a = s.charAt(i), b = s.charAt(j);
            if (!Character.isLetterOrDigit(a)) i++;
            else if (!Character.isLetterOrDigit(b)) j--;
            else if (Character.toLowerCase(a) != Character.toLowerCase(b)) return false;
            else { i++; j--; }
        }
        return true;
    }
}

Common mistakes

Forgetting digits are alphanumeric ("0P" is not a palindrome).

3Sum · Medium
Container With Most Water · Medium