// Valid Palindrome

task

Given a string s, determine whether it reads the same forwards and backwards once you ignore casing and drop everything that isn’t a letter or digit.

s = "A man, a plan, a canal: Panama"  →  true (ignoring case and punctuation/spaces)

how to think

The brute force builds a cleaned copy — strip punctuation, lowercase everything, compare to its own reverse. That’s correct and O(n), but it’s also O(n) space for a string you’re not otherwise using, and “in-place, O(1) space” is exactly the phrase that should make you reach for opposite-end pointers instead.

The only wrinkle versus vanilla Two Sum II is that a pointer can’t always compare where it’s standing — first it has to ask “am I looking at something that counts?” If not, step past it and ask again. Once both pointers are parked on real alphanumeric characters, the comparison is the same case-insensitive check either way.

solution

public bool IsPalindrome(string s)
{
    int left = 0, right = s.Length - 1;

    while (left < right)
    {
        if (!char.IsLetterOrDigit(s[left])) { left++; continue; }
        if (!char.IsLetterOrDigit(s[right])) { right--; continue; }

        if (char.ToLowerInvariant(s[left]) != char.ToLowerInvariant(s[right])) return false;

        left++;
        right--;
    }
    return true;
}

trace

s = "race a car" (index 4 and 6 are spaces):

Step 4 — right sits on a space, so it steps past it while left holds still:

Step 5 — both pointers now sit on letters, and they disagree:

why it works

The invariant is symmetric: at the start of every iteration, every character strictly outside [left, right] has either matched its mirror or been ruled irrelevant. left and right only ever move inward, so the two pointers cross after at most s.Length total steps. If they cross without a mismatch, there was nothing left to check — the string is a palindrome under the ignore-case/ignore-punctuation rule. One disagreement is sufficient to disprove it immediately, which is why the function returns false the instant it finds one instead of finishing the scan.

common bugs

• Comparing case-sensitively — forgetting char.ToLowerInvariant (or ToUpperInvariant) turns "Aa" into a false mismatch.
• Using the culture-sensitive char.ToLower(c) instead of the invariant form: on some locales (Turkish is the classic example) case folding doesn’t behave the way you’d expect, and an interview solution should never depend on the machine’s locale.
• Only skipping non-alphanumerics on one side — both left and right need their own independent skip check, not a single shared one.
• Building a cleaned string first (new string(s.Where(char.IsLetterOrDigit).ToArray())) — it works, but it’s O(n) space when the problem is explicitly asking for O(1).
• Forgetting that an empty string, or a string of pure punctuation, is vacuously a palindrome — the loop never runs and the function correctly falls through to true.

variants you can now solve

• Valid Palindrome II (LC 680) — same scan, but on a mismatch you get to skip one character on either side and check both resulting substrings before giving up.
• Longest Palindromic Substring (LC 5) — instead of checking one fixed string, you expand outward from every possible center.
• Palindrome Linked List (LC 234) — the same mirror-compare idea, but you have to find the middle and reverse a half first since you can’t walk a linked list backwards.