One Deletion Palindrome
MediumTwo Pointers
Problem
A spell-checker flags words that are *almost* palindromes. Given a lowercase string s, return true if s reads the same forwards and backwards after deleting at most one character, and false otherwise.
Example 1
- Input:
- s = "racexcar"
- Output:
- true
Deleting the "x" leaves "racecar".
Example 2
- Input:
- s = "abcda"
- Output:
- false
Whatever single character you delete, the inner part 'bcd' cannot become a palindrome.
Example 3
- Input:
- s = "level"
- Output:
- true
Already a palindrome; no deletion is needed.
Constraints
- 1 ≤ s.length ≤ 10^5
- s consists of lowercase English letters
Hint
Show the first hint
Compare from both ends as for a normal palindrome. What happens at the first mismatch?
Walkthrough
How to approach it
01Clarify before coding
- Is deleting zero characters allowed? Yes, a palindrome already qualifies.
- Exactly one deletion at most, not one per side? Yes, one in total.
- Only lowercase letters? Yes, no normalisation needed.
02Brute force
For each position, delete it and test whether the result is a palindrome; also test the original.
Cost: O(n²) time: n candidates, each checked in O(n). Too slow for n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.