Valid Palindrome

Q: What is the time complexity of Valid Palindrome?

Both approaches run in O(n) time, because every character is looked at a constant number of times. Cleaning first uses O(n) extra memory for the copy. The two pointer version uses O(1) extra memory, since it only keeps two indexes.

Q: How do you check a palindrome while ignoring non alphanumeric characters?

Keep one pointer at each end of the string. Move a pointer past any character that is not a letter or digit, and when both rest on letters or digits, compare them in lower case. If every compared pair matches until the pointers meet, the string is a palindrome.

Q: Is an empty string a palindrome?

Yes. An empty text reads the same in both directions, so a string such as ?!-_ , whose characters are all ignored, returns true . Both approaches get this without extra code: the cleaned text equals its empty reverse, and the two pointers never find a pair that differs.

Q: Why use two pointers instead of reversing the string?

Reversing needs a cleaned copy and a reversed copy, which is O(n) extra memory. Two pointers compare the same pairs in place, and they can stop at the first mismatch, often after a few steps. Interviewers usually ask for this version as the follow-up.

EasyTwo pointers

+10

You get a string s. Keep only its letters and digits, treat upper and lower case as the same letter, and decide whether what is left reads the same from left to right as from right to left. Return true if it does and false otherwise.

Every other character, such as ., !, ?, :, ;, - or _, is ignored. If s has no letters or digits at all, nothing is left, and an empty text counts as a palindrome.

Function

isPalindrome(s: string) → boolean

sstring: the text to check, punctuation included
Returnsboolean: true if the letters and digits of s read the same in both directions, ignoring case

Constraints

1 ≤ s.length ≤ 5 × 10⁴
s contains English letters, digits and the punctuation marks . ! ? : ; - _, with no spaces.

Examples

Input: s = "Was_it_a_car_or_a_cat_I_saw?"
Output: true
Explanation: Drop the underscores and the question mark and lower the capitals: you get wasitacaroracatisaw, which is the same backwards.

Input: s = "race-a-car"
Output: false
Explanation: Without the hyphens the text is raceacar. Read from the right it starts raca instead of race: the e in the middle has an a as its mirror partner, so the answer is false.

Input: s = "Step-on-no-pets!"
Output: true
Explanation: The kept text is steponnopets. The capital S matches the final s because case is ignored, and the hyphens and the ! play no part.

+25 hidden tests on Submit

Follow-up

Can you decide it with O(1) extra memory, without building a cleaned copy of s?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The palindrome check itself is the familiar one: the first kept character must equal the last, the second must equal the second to last, and so on. What makes this version tricky is that the characters you compare are not at mirrored indexes of s, because punctuation is scattered unevenly on the two sides. You can remove it first, or let two pointers step over it as they walk toward each other.

Clean the string, then compare it with its reverse

Intuition

Build the text the problem actually asks about. Walk through s, keep each letter or digit in lower case, and skip everything else. For Step-on-no-pets! that gives steponnopets. Now the question is the plain palindrome question: is this text equal to its own reverse?

This is correct because cleaning removes exactly the characters the problem says to ignore and folds the case it says to ignore. If s holds no letters or digits, the cleaned text is empty, and an empty text equals its reverse, so the answer is true with no special case.

Each character is read once to clean and once more to compare, so the time is O(n). The cleaned copy and its reverse take O(n) extra memory, which is the cost the next approach removes.

Algorithm

Create an empty text cleaned.
For each character of s, if it is a letter or digit, append it in lower case.
Reverse cleaned.
Return whether cleaned equals its reverse.

def isPalindrome(s):
    cleaned = [ch.lower() for ch in s if ch.isalnum()]
    return cleaned == cleaned[::-1]

Two pointers that skip punctuation

Intuition

The cleaned copy is only there so you can compare mirrored characters. You can do the same comparison on s directly. Put left on the first index and right on the last. At each step, if left points at punctuation, move it right; if right points at punctuation, move it left. Once both point at letters or digits, compare them in lower case. A mismatch means false; a match means both pointers step inward.

Why is this the same check? The pointers always stop on the next kept character from each end, so they visit the pairs (first kept, last kept), (second kept, second to last kept) and so on, which are exactly the pairs the reverse comparison looks at. In Abc-dcbX the first pair is A and X, and the answer is false after one comparison.

Each step moves at least one pointer, and they stop when they meet, so the loop runs at most n times. Apart from the two indexes nothing is stored, which gives O(1) extra memory.

Algorithm

Set left = 0 and right = n-1.
While left < right: if s[left] is not a letter or digit, increase left and continue.
Otherwise, if s[right] is not a letter or digit, decrease right and continue.
Otherwise compare the two characters in lower case. If they differ, return false; if they match, move both pointers inward.
When the pointers meet, return true.

def isPalindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if not s[left].isalnum():
            left += 1
        elif not s[right].isalnum():
            right -= 1
        elif s[left].lower() != s[right].lower():
            return False
        else:
            left += 1
            right -= 1
    return True

Pitfalls and edge cases

Most bugs come from the characters that are skipped and from case.

Comparing s[i] with s[n-1-i] on the raw string. a-ba is a palindrome once the hyphen is dropped, but the raw mirror of the - at index 1 is the b at index 2.
Moving both pointers when only one of them sits on punctuation. Skip on one side at a time, or the two sides drift out of step.
Skipping punctuation in an inner loop that runs past the other pointer. With ?!-_ an unbounded inner loop walks off the end of the string; keep the left < right check on every move.
Treating digits as noise. 0P is false: the digit 0 is kept and compared, and it is not the letter p.
Returning false when nothing is kept. A string of punctuation only, such as ., has an empty cleaned text, which is a palindrome.
A string made only of digits, such as 12321, can reach PHP and R as a number. Convert it to a string first.

Frequently asked questions4

What is the time complexity of Valid Palindrome?

Both approaches run in O(n) time, because every character is looked at a constant number of times. Cleaning first uses O(n) extra memory for the copy. The two pointer version uses O(1) extra memory, since it only keeps two indexes.

How do you check a palindrome while ignoring non alphanumeric characters?

Keep one pointer at each end of the string. Move a pointer past any character that is not a letter or digit, and when both rest on letters or digits, compare them in lower case. If every compared pair matches until the pointers meet, the string is a palindrome.

Is an empty string a palindrome?

Yes. An empty text reads the same in both directions, so a string such as ?!-_, whose characters are all ignored, returns true. Both approaches get this without extra code: the cleaned text equals its empty reverse, and the two pointers never find a pair that differs.

Why use two pointers instead of reversing the string?

Reversing needs a cleaned copy and a reversed copy, which is O(n) extra memory. Two pointers compare the same pairs in place, and they can stop at the first mismatch, often after a few steps. Interviewers usually ask for this version as the follow-up.

Python

def isPalindrome(s):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

s = "Was_it_a_car_or_a_cat_I_saw?"

Expected

true