Valid Palindrome II
The key idea
Walk two pointers inward from both ends. As long as the characters match, the outside is a palindrome and you keep going. At the FIRST mismatch you have exactly one deletion to spend, and only two candidates make sense: drop the left char or drop the right char. Check whether the substring between them (skipping one side) is a plain palindrome — if either skip works, the answer is
true.Problem
Given a string s, return true if s can be a palindrome after deleting at most one character from it.
A palindrome reads the same forward and backward. You may delete zero or one character; deleting 0 is allowed when s is already a palindrome.
Constraints
1 <= s.length <= 10^5sconsists of lowercase English letters.
Examples
Input: s = "aba"
Output: true
Input: s = "abca"
Output: true
Input: s = "abc"
Output: false
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Two Pointers problems
- 3SumMEDIUM
- 4SumMEDIUM
- Concatenation of ArrayEASY
- Container With Most WaterMEDIUM
- Is SubsequenceEASY
- Merge Sorted ArrayEASY
- Merge Strings AlternatelyEASY
- Move ZeroesEASY
- Next PermutationMEDIUM
- Remove Duplicates from Sorted ArrayEASY
- Remove Duplicates from Sorted Array IIMEDIUM
- Remove ElementEASY