Valid Palindrome

Difficulty: Easy

Problem

Return true if the string s reads the same forwards and backwards once every character that is not a letter or digit is dropped and uppercase and lowercase are treated as equal; otherwise return false.

Example

Input: s = "Was it a car or a cat I saw?"
Output: true
Explanation: After removing spaces and punctuation and lowercasing, the text is "wasitacaroracatisaw", which reads the same in both directions.

Brute-force approach

Create a cleaned string (alphanumeric only, lowercase), reverse it, and compare with original cleaned string.

Steps

  1. Keep only letters and digits, convert to lowercase
  2. Create reversed string of the cleaned string
  3. Compare: if equal → palindrome, else → not a palindrome

Time complexity: O(n) · Space complexity: O(n)

Trade-offs

  • Creates extra strings
  • Uses O(n) extra space
  • Can we avoid copying?

Optimal approach

Key insight: A palindrome reads same forwards and backwards. Compare from both ends simultaneously!

Use two pointers from both ends, skip non-alphanumeric, compare in-place.

Steps

  1. Left pointer at start, right at end
  2. Skip non-alphanumeric characters
  3. Compare characters (case-insensitive)
  4. Move pointers inward

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

Pseudocode

function isPalindrome(s):
    left = 0
    right = length of s - 1
    
    while left < right:
        while left < right and s[left] is not alphanumeric:
            left++
        while left < right and s[right] is not alphanumeric:
            right--
        
        if lowercase(s[left]) != lowercase(s[right]):
            return false
        
        left++
        right--
    
    return true

Hints

  • Use two pointers from both ends
  • Skip non-alphanumeric characters
  • Compare characters case-insensitively

Complexity questions

What is the time complexity of the brute force (reverse string) approach?

O(n). O(n) to clean, O(n) to reverse, O(n) to compare = O(n) total.

What is the space complexity of the brute force approach?

O(n). O(n) for the cleaned string + O(n) for the reversed string = O(n).

What is the time complexity of the two pointers approach?

O(n). Each pointer moves at most n/2 positions = O(n) total.

What is the space complexity of the two pointers approach?

O(1). Only two pointer variables are used, regardless of input size.

Check your understanding of Valid Palindrome

What is a palindrome?

A word that reads the same forwards and backwards. A palindrome reads the same forwards and backwards, like 'racecar' or 'madam'.

Is 'A man, a plan, a canal: Panama' a valid palindrome?

Yes, when ignoring non-alphanumeric characters and case. Ignoring spaces and punctuation, it reads 'amanaplanacanalpanama' - a palindrome.

What should 'race a car' return?

false - 'raceacar' is not a palindrome. After removing spaces: 'raceacar' ≠ 'racacear', so it's not a palindrome.

Related problems

Keep practising