Valid Palindrome II
Pick a vanity handle that reads the same from both ends. You get a handle made of lowercase letters. You may remove at most one letter (or none). Return true if what is left reads the same forwards and backwards, and false if no single removal gets you there. Limits: 1 to 400,000 letters, all from a to z. Re-checking the whole handle after every possible removal is far too slow at that size, and a recursive scan can overflow the stack, so use a loop. Think about: when the two letters at the ends disagree, which one is the odd one out? Example: "racecars" => true (remove the last s and "racecar" mirrors itself) "deified" => true (already a mirror, nothing to remove) "plank" => false (no single removal leaves a mirror)
You're checking whether a handle reads the same from both ends once you're allowed to drop a single letter. Interviewers love it because the two-pointer scan is easy right up to the first mismatch, and then you have to decide which side to blame. The classic trap is trying only one of the two options, or deleting every letter in turn and re-checking the whole handle. Expect up to 400,000 lowercase letters.
Examples
You write
valid_palindrome_ii(s: str)
Example 1
- Input
- s = "racecars"
- returns
- true
Example 2
- Input
- s = "deified"
- returns
- true
Save this for your laptop
The editor and Run need a bigger screen. The link opens Valid Palindrome II ready to code. It is free, and the editor needs no account.
The pattern behind it
Two Pointers
I reach for it when
- The array is sorted, or you can sort it.
- You need a pair, a triple or a palindrome.
Say this before you type. Say what each pointer means and what a move to the left or right rules out.
All 26 Two Pointers problemsStrings
I reach for it when
- The input is text and the answer is a count, a substring or a new string.
- You need to compare, reverse or rebuild characters.
Say this before you type. Say which array pattern the string is hiding before you touch a character.
All 49 Strings problems
Meet Coco
Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.