Two Pointers · 171Easy
Valid Palindrome II
Given a string s, return true if s can be a palindrome after deleting AT MOST one character from it.
Constraints
- 1 <= s.length <= 10^5
- s consists of lowercase English letters.
Examples
validPalindrome("aba") -> true // already a palindrome
validPalindrome("abca") -> true // delete 'c' (or 'b')
validPalindrome("abc") -> false
validPalindrome("a") -> true // a single character
validPalindrome("aaaa") -> true // all-same, no deletion needed
validPalindrome("cuppucu") -> true // only deleting the RIGHT side worksEdge cases
- At the first mismatch you may have to try BOTH deletions: skipping the left character can
- fail where skipping the right one succeeds ("cuppucu").
- A single character is a palindrome.
Show the target complexity (spoiler)
- Naive
- O(n^2) time — delete each character in turn and check the remainder.
- Target
- O(n) time, O(1) space — two pointers; at the first mismatch, check whether s[l+1..r] or s[l..r-1] is a palindrome.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/02-two-pointers/171-valid-palindrome-ii.js ./practice c 171