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: 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 stop at the first mismatch, often after a few steps.

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. 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.

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 check is the usual one: the first kept character must equal the last, the second the second to last, and so on. The catch is that kept characters do not sit at mirrored indexes of s, because punctuation is scattered unevenly. Remove it first, or let two pointers step over it as they walk inward.

Clean the string, then compare it with its reverse

Intuition

Walk through s, keep each letter or digit in lower case, and skip the rest: Step-on-no-pets! becomes steponnopets. Cleaning removes exactly what the problem says to ignore, so the answer is whether this text equals its reverse. A string with no letters or digits cleans to the empty text, which equals its reverse, with no special case.

The time is O(n), and the copy and its reverse take O(n) extra memory.

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 only exists to compare mirrored characters, and you can compare them on s directly. Step each pointer past punctuation, then compare the two characters in lower case. The pointers always stop on the next kept character from each end, so they visit (first kept, last kept), (second kept, second to last kept) and so on: exactly the pairs the reverse comparison checks.

Each step moves at least one pointer, so the loop runs at most n times, and only two indexes are stored. It also stops at the first mismatch: Abc-dcbX is false after comparing A with X.

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

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 sits on punctuation. Skip on one side at a time, or the two sides drift out of step.
Skipping punctuation in an inner loop with no left < right check. On ?!-_ it walks off the end of the string.
Treating digits as noise. 0P is false: the 0 is kept, and it is not the letter p.
In PHP and R, a string of digits such as 12321 can arrive as a number. Convert it to a string first.

Frequently asked questions3

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.

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 stop at the first mismatch, often after a few steps.

def isPalindrome(s):
    # Write code here

Test #1

Test #2

Test #3

Argument

s = "Was_it_a_car_or_a_cat_I_saw?"

Expected Output

true