EasyTwo PointersString

Valid Palindrome

1 approach, code in every language

You are given a string that may contain letters, digits, spaces, and punctuation. The task is to decide whether the string reads the same forward and backward once you ignore everything that is not a letter or a digit, and once you treat uppercase and lowercase letters as equal.

Return true when the cleaned-up version of the string is a palindrome, and false otherwise. An empty string (after filtering) counts as a palindrome.

Example 1

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

Output: true

After removing punctuation and spaces and lowercasing, the text becomes "amanaplanacanalpanama", which mirrors itself.

Example 2

Input: s = "race a car"

Output: false

The filtered text "raceacar" differs when read backward, so it is not a palindrome.

Constraints

1 ≤ s.length ≤ 2 * 10^5
s consists only of printable ASCII characters.

Two Pointers From Both Ends

Walk one index in from the left and one in from the right, skipping any character that is not alphanumeric, and compare the surviving characters case-insensitively.

Loading animation…

Intuition

A palindrome is symmetric, so the character we meet coming from the front should match the character we meet coming from the back. Instead of building a filtered copy of the string, we can move two indices toward the middle and simply hop over characters we are told to ignore. Whenever both pointers land on real letters or digits, they must agree after lowercasing; the first disagreement proves the string is not a palindrome.

Algorithm walkthrough

1Place a left index at the start of the string and a right index at the last position.
2Advance the left index while it points at a non-alphanumeric character, and pull the right index back while it points at a non-alphanumeric character.
3Compare the two characters after converting both to lowercase; if they differ, return false immediately.
4Otherwise step the left index forward and the right index backward and repeat.
5When the two indices meet or cross, every pair matched, so return true.

Implementation

class Solution:
    def isPalindrome(self, 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

Time

O(n)

Space

O(1)

Each index moves toward the center only, so every character is visited at most once.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Strings

After the pattern

Now solve one you haven't seen.

Mirror Phrase Check is our own problem on the technique behind Valid Palindrome: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free