1. Valid Palindrome II (LeetCode)
Model answer
The task
Determine whether a string can become a palindrome after removing at most one character.
Key idea
Compare characters from both ends, moving inward while they match. At the first mismatch, the one allowed removal must skip either the left character or the right character; check whether either remaining range is a palindrome.
Approach
- Initialize pointers at the start and end of the string.
- While the pointed-to characters match, move both pointers inward.
- If the pointers meet, the string is already a palindrome.
- Otherwise, check the two ranges formed by skipping either mismatched character.
- Return true if at least one range is a palindrome.
class Solution:
def validPalindrome(self, s: str) -> bool:
def is_palindrome(left: int, right: int) -> bool:
# Check whether this inclusive range reads the same both ways.
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
# Use the one allowed deletion on either mismatched end.
return (
is_palindrome(left + 1, right)
or is_palindrome(left, right - 1)
)
left += 1
right -= 1
return True
Complexity:
- Time: O(n), since at most two linear range checks are performed.
- Space: O(1), excluding the input string; the checks use only pointers.
Common follow-ups
- What if up to
kcharacters may be removed? Use recursion or dynamic programming to track the remaining deletion budget; the simple one-mismatch check no longer suffices. - What if the input is a linked list? Use a stack or find the midpoint and reverse part of the list, depending on whether extra space is allowed.
- Should comparison ignore capitalization or punctuation? Normalize or skip irrelevant characters while moving the two pointers inward.