125. One Delete Away
A word game accepts a word if it reads the same forwards and backwards, which is called a palindrome. A player may help a word by deleting at most one letter anywhere in it, and the remaining letters keep their order.
Given the string s of lower case letters, return true if it can be turned into a palindrome after deleting at most one character, and false otherwise. A word that is already a palindrome qualifies without any deletion. Use two pointers from both ends and try the two possible deletions only at the first mismatch.
Example 1
- Input:
- s = "racecars"
- Output:
- true
- Explanation:
Deleting the last letter s leaves racecar, which is a palindrome.
Example 2
- Input:
- s = "abcde"
- Output:
- false
- Explanation:
Removing one letter can never fix the many mismatching pairs, so the answer is false.
Constraints
1 ≤ s.length ≤ 105
s contains only lower case English letters
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)