The O(n) Club: Valid Palindrome II: Palindrome With Training Wheels

The O(n) Club: Valid Palindrome II – Palindrome With Training Wheels

⚡ TL;DR

Basically, you get one free pass. Given a string, can it be a palindrome if you delete one (and only one) character? Two-pointer it like a boss:

// Java quickstart
public boolean validPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
        }
        left++;
        right--;
    }
    return true;
}
private boolean isPalindrome(String s, int left, int right) {
    while (left < right) {
        if (s.charAt(left++) != s.charAt(right--)) return false;
    }
    return true;
}

🧠 How Devs Usually Mess This Up

Ah, the classics! Some folks bring baggage from the original Palindrome problem: unnecessary string cleanup, case mangling, and the inevitable mini-regex meltdown. Others short-circuit the challenge by skipping only one letter—left or right, never both, so “abca” fails gloriously. Pro tip: if your code panics at edge cases, the interviewer will too.

🔍 What’s Actually Going On

Imagine two suspicious pointer-bots starting at opposite ends of a string, inching closer with every check. If everything matches, great, you have a bona-fide palindrome and can go to lunch early. If the bots catch a mismatch, you get one—just one—chance to ditch the troublemaker (either left or right) and see if palindrome peace is restored. If not, it’s time to swipe left on symmetry.

🛠️ PseudoCode

• Set left = 0 and right = s.length() - 1.
• As long as left < right:
  • If s.charAt(left) == s.charAt(right), move both pointers inward.
  • If not, check if either s[left+1...right] or s[left...right-1] is a palindrome.
  • If either works, high five yourself.
• If no mismatches, string is already a palindrome. Bask in that glory.

💻 The Code

public boolean validPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
        }
        left++;
        right--;
    }
    return true;
}
private boolean isPalindrome(String s, int left, int right) {
    while (left < right) {
        if (s.charAt(left++) != s.charAt(right--)) return false;
    }
    return true;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• If you only skip one side, you’re just collecting “almost correct” rejections. Check both sides.
• Skip the whole lowercase/regex circus. That’s Valid Palindrome I, not this gig.
• Edge cases: empty strings and single chars are always palindromes. Strings of all the same letter? They wish you’d give them something to do.
• Time complexity: O(n). Space: O(1) (your only real baggage is emotional).

🧠 Interviewer Brain-Tattoo

“Skipping the wrong character is how palindromes—and careers—get broken.” And yes, ‘abca’ tests if you’ve ever even glanced at the other side.