Valid Palindrome II
Last Updated: March 29, 2026
Understanding the Problem
We need to determine whether a string is "almost" a palindrome. That means it either already reads the same forwards and backwards, or it can become one by removing exactly one character.
The naive instinct is to try removing each character one at a time and checking if the result is a palindrome. But with strings up to 100,000 characters long, we need to be smarter. The key observation is this: if we check from both ends using two pointers and they match, great, keep going. But the moment they don't match, we have exactly two choices: skip the left character or skip the right character. If either of those remaining substrings is a palindrome, the answer is true. If neither works, the answer is false.
Key Constraints:
1 <= s.length <= 10^5→ With n up to 100,000, an O(n^2) approach that tries every possible deletion (n deletions, each requiring an O(n) palindrome check) would mean 10^10 operations, which is way too slow. We need O(n) or O(n log n).sconsists of lowercase English letters → No need to worry about case sensitivity, spaces, or special characters. Simplifies character comparison.
Approach 1: Brute Force
Intuition
The most direct approach: try deleting each character one at a time, and check if the resulting string is a palindrome. If any deletion produces a palindrome, return true. Also check if the original string is already a palindrome (which counts as "deleting zero characters").
This is straightforward but expensive. For each of the n possible deletions, we do an O(n) palindrome check, giving us O(n^2) total work.
Algorithm
- First, check if the original string is already a palindrome. If yes, return true.
- For each index
ifrom0ton - 1: - Create the string with character at index
iremoved. - Check if this new string is a palindrome.
- If it is, return true.
- If no single deletion produces a palindrome, return false.
Example Walkthrough
Code
- Time Complexity: O(n^2). We try n possible deletions, and each palindrome check takes O(n) time.
- Space Complexity: O(n). Each deletion creates a new string of length n - 1.
This works but is way too slow for strings up to 100,000 characters. What if instead of trying every deletion, we only checked the one or two positions where a deletion could actually help?
Approach 2: Two Pointers (Greedy)
Intuition
Start two pointers at both ends of the string and move them inward. As long as the characters match, there's no problem. The moment they don't match, we've found the only spot where a deletion could help.
At that mismatch, we have exactly two options: delete the character on the left (and check if s[left+1..right] is a palindrome) or delete the character on the right (and check if s[left..right-1] is a palindrome). If either option works, the answer is true. If neither does, no single deletion can save this string.
The correctness relies on a simple observation: if two characters at mirror positions match, neither of them needs to be deleted. Deleting a matching character would just create a new problem without solving anything. So we can safely skip past all matching pairs. The first mismatch is the only point where our single deletion can make a difference.
Once we're at the mismatch, we have exactly two candidates for deletion. We try both and check if the remaining substring is a valid palindrome. Since we only do this once (at most one mismatch to handle), the total work is still O(n).
Algorithm
- Initialize two pointers:
left = 0andright = s.length - 1. - Move them inward while
s[left] == s[right]. - If we reach
left >= rightwithout a mismatch, the string is already a palindrome. Return true. - At the first mismatch, check two options:
- Is
s[left+1..right]a palindrome? (skip left character) - Is
s[left..right-1]a palindrome? (skip right character) - Return true if either option is a palindrome, false otherwise.
Example Walkthrough
Code
- Time Complexity: O(n). The outer loop scans at most n/2 characters. On a mismatch, the helper checks at most n/2 more. Total work is at most n comparisons.
- Space Complexity: O(1). Only a few integer variables for the pointers. No extra data structures or string copies.