Palindrome After One Deletion
Problem
A word game accepts a string if it reads the same forwards and backwards, and it forgives a single typo. Given a string s of lowercase letters, return True if s is already a palindrome or becomes one after deleting exactly one character, and False otherwise. The empty string counts as a palindrome.
Examples
Input: s = "racexcar"
Output: True
Why: deleting the x leaves "racecar"Input: s = "abcda"
Output: False
Why: after the outer a's match, b and d disagree, and dropping either one still failsInput: s = ""
Output: True
Why: edge case, nothing to compare, so no deletion is neededHints
0 / 3
Trying every possible deletion and checking each result is quadratic. Most of the string never needs a second look.
Walk two pointers inward from both ends. As long as the characters match, no decision is needed. The only interesting moment is the first mismatch.
At the first mismatch the deleted character must be one of the two under the pointers. Check whether the inner stretch without the left one, or without the right one, is a palindrome on its own. If the pointers meet with no mismatch, the answer is already yes.
Solution
Matching outer characters can never be the problem, so the two pointers skip over them without spending the one deletion. At the first mismatch, any fix must delete one of those two characters, since every character outside them already has its partner. That leaves exactly two candidate substrings, each checked with a plain palindrome scan, and no further choices appear inside them. Time is O(n) because each character is compared at most a few times, and space is O(1).
def almost_palindrome(s):
def is_pal(i, j): # plain two-pointer check of s[i..j]
while i < j:
if s[i] != s[j]:
return False
i, j = i + 1, j - 1
return True
i, j = 0, len(s) - 1
while i < j:
if s[i] != s[j]:
# the one deletion must remove s[i] or s[j]
return is_pal(i + 1, j) or is_pal(i, j - 1)
i, j = i + 1, j - 1
return True
print(almost_palindrome("racexcar")) # -> True
print(almost_palindrome("abcda")) # -> False
print(almost_palindrome("")) # -> TrueStuck on the idea rather than the code? Valid Palindrome covers it.