Valid Palindrome II

EASY✓ CHIP-TIMEDLC #680 — FULL STATEMENT ↗

The drill: A near-palindrome test: the string earns its pass if deleting at most one character — or none at all — leaves something that reads identically both ways. The whole game is what you do at the first mismatch.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A string arrives with one allowance: you may delete a single character from it — or none at all — and the question is whether some choice of that single deletion leaves a string that reads identically forwards and backwards.

The deletion, if used, can come from anywhere in the string, not just the ends. Using zero deletions is always a legal choice when the string is already a palindrome.

Only one character total may ever be removed; needing two or more disqualifies the string. The answer is a simple yes or no, not the resulting string itself.

EX 01

s = "repaper"

→ true

ALREADY A PALINDROME — ZERO DELETIONS

EX 02

s = "radkar"

→ true

MIDDLE MISMATCH, EITHER SIDE WORKS

EX 03

s = "acbba"

→ true

ONLY THE LEFT SKIP SAVES IT

string length runs up to roughly one hundred thousand lowercase letters
at most one character may be deleted, from any position
using zero deletions is allowed when the string already qualifies
the result reported is a boolean, not the surviving string

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Deleting every candidate character and re-checking works, but it re-reads the whole string n times — and almost every one of those deletions was never in doubt.

HINT 2 THE STRUCTURE

Walk inward from both ends. While the two characters agree there is nothing worth deleting — the only real decision point is the first disagreement.

HINT 3 ONE STEP FROM THE ANSWER

At the first mismatch you get one skip: drop the left character or drop the right one, and whichever remainder you keep must be a plain palindrome. Check both; either passing is a yes.

COACH'S BOARD — THE PATTERN, STEP BY STEP

ONE SKIP AT THE MISMATCHPATTERN · TWO POINTERS + ONE ALLOWED SKIPs = "abbca"

STEP 1

Walk inward while characters agree; the only real decision is at the first disagreement.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/valid-palindrome-ii.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def is_pal(l, r):
            while l < r:
                if s[l] != s[r]:
                    return False
                l += 1
                r -= 1
            return True

        l, r = 0, len(s) - 1
        while l < r:
            if s[l] != s[r]:
                # one skip allowed: drop the left char or the right char
                return is_pal(l + 1, r) or is_pal(l, r - 1)
            l += 1
            r -= 1
        return True

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

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def is_pal(t):
            return t == t[::-1]

        if is_pal(s):
            return True
        for i in range(len(s)):
            if is_pal(s[:i] + s[i + 1:]):
                return True
        return False

TIME O(N²)SPACE O(N)PYTHON · TRAINING PACE · 11 LN

class Solution {
    public boolean validPalindrome(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) {
                // one skip allowed: drop the left char or the right char
                return isPal(s, l + 1, r) || isPal(s, l, r - 1);
            }
            l++;
            r--;
        }
        return true;
    }

    private boolean isPal(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }
}

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

class Solution {
    public boolean validPalindrome(String s) {
        if (isPal(s)) return true;
        for (int i = 0; i < s.length(); i++) {
            String t = s.substring(0, i) + s.substring(i + 1);
            if (isPal(t)) return true;
        }
        return false;
    }

    private boolean isPal(String t) {
        int l = 0, r = t.length() - 1;
        while (l < r) {
            if (t.charAt(l) != t.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }
}

TIME O(N²)SPACE O(N)JAVA · TRAINING PACE · 20 LN

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