Valid Palindrome II
Easy · Two Pointers · Two Pointers · String · Greedy
Problem
Given a string s, return true if it can be turned into a palindrome by deleting at most one character, and false otherwise.
Deleting nothing is allowed, so a string that is already a palindrome returns true.
Examples
Input: s = "racecfar" Output: true
Deleting the "f" leaves "racecar".
Input: s = "abcca" Output: true
Deleting the "b" leaves "acca".
Input: s = "abcdea" Output: false
After the outer pair of a’s, "bcde" remains; deleting either b or e still leaves a string that is not a palindrome.
Constraints
- 1 <= len(s) <= 10^5
- s consists of lowercase English letters
Approaches
- Baseline: delete each letter in turn — time O(n²), space O(n)
Follow-up
What if up to k deletions are allowed? Branching at every mismatch becomes exponential; instead compare k with n minus the longest palindromic subsequence (see the use case “Palindrome after at most k deletions”).
Related problems
Start free on Cariara · Coding problems · System design studio
