A typo checker gets words that should read the same forwards and backwards, but one stray key press may have slipped in somewhere.
Write palindrome_after_one_delete(s: str) -> bool: return True if you can make s read the same both ways by deleting at most one character (deleting none is fine too), and False otherwise.
palindrome_after_one_delete("level") # True (already reads the same both ways)
palindrome_after_one_delete("kayaks") # True (delete the last "s": "kayak")
palindrome_after_one_delete("tooth") # True (delete the "h": "toot")
palindrome_after_one_delete("parrot") # False (no single deletion works)
palindrome_after_one_delete("abaab") # True (delete the first "a": "baab")
Constraints: 1 <= len(s) <= 10^5; s has only lowercase letters a-z.
⭐ Bonus: trying every possible deletion and checking the rest is O(n²) and still passes; a speed test on 10^5 letters earns a star in O(n).
Show hint
compare from both ends. Everything is fine until the first pair that doesn't match; at that point one of those two characters has to go, and there are only two ways to choose.