Valid Palindrome

EASY✓ CHIP-TIMEDLC #125 — FULL STATEMENT

The briefingthe full drill, in my own words

The drill: Decide whether a sentence reads the same forwards and backwards once punctuation, spaces and letter case are stripped away — only letters and digits get a vote. The classic warm-up for walking a string from both ends at once.

A sentence arrives, likely dressed up with punctuation, spaces, and mixed-case letters, and the question is whether it reads the same forwards and backwards once all that dressing is ignored.

Only letters and digits count toward the comparison; case is irrelevant, so 'A' and 'a' are treated as identical. Everything else — spaces, commas, apostrophes — is skipped entirely rather than compared.

An empty string, or a string with nothing but punctuation, reads as a palindrome by default since there is nothing left to disagree.

string length runs from empty up to a couple hundred thousand characters
input may include letters, digits, spaces, and punctuation in any mix
comparisons ignore case and skip every non-alphanumeric character
strings with no letters or digits at all count as valid

EX 01

s = "Draw, o coward!"

→ true

punctuation and spaces ignored

EX 02

s = "pace"

→ false

EX 03

s = "., !?"

→ true

pure punctuation — nothing left to compare

The hintstake only what you need

HINT 1 THE NUDGE

Cleaning the string first — drop the noise, lowercase the rest — makes the check trivial, but that cleaned copy is exactly the O(n) space worth shedding.

HINT 2 THE STRUCTURE

A palindrome check never needed a copy: compare the outermost characters and walk inward. The noise just means some characters don't deserve a comparison at all.

HINT 3 ONE STEP FROM THE ANSWER

Two pointers at the ends; each skips inward past non-alphanumerics before comparing lowercased characters. Any mismatch ends it — the pointers crossing means it read clean.

Coach's boardthe pattern, step by step

SKIP AND COMPAREPATTERN · TWO POINTERSs = ".a,a."

STEP 1

Pointers L and R start at the ends: index 0 and index 4. Only letters and digits get compared.

STEP 1 / 6 · ← → WORK TOO

The splitstwo paces, two languages

grind/valid-palindrome.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def isPalindrome(self, s: str) -> bool:
        l, r = 0, len(s) - 1
        while l < r:
            while l < r and not s[l].isalnum():
                l += 1
            while l < r and not s[r].isalnum():
                r -= 1
            if s[l].lower() != s[r].lower():
                return False
            l += 1
            r -= 1
        return True

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 13 LN

class Solution {
    public boolean isPalindrome(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) {
            while (l < r && !Character.isLetterOrDigit(s.charAt(l))) l++;
            while (l < r && !Character.isLetterOrDigit(s.charAt(r))) r--;
            if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r))) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 15 LN

class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder kept = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                kept.append(Character.toLowerCase(c));
            }
        }
        String forward = kept.toString();
        String backward = kept.reverse().toString();
        return forward.equals(backward);
    }
}

TIME O(N)SPACE O(N)JAVA · TRAINING PACE · 13 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED