Valid Palindrome II
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 at most one character.
One way to solve this is to remove each character one at a time and check whether the result is a palindrome. With strings up to 100,000 characters, that is too slow. A faster idea: scan from both ends with two pointers. While the mirrored characters match, move inward. At the first mismatch, exactly one of two characters must be the one we delete, the one at the left pointer or the one at the right pointer. Check whether skipping either one leaves a palindrome. If so, the answer is true; if neither works, no single deletion can fix the string.
Key Constraints:
1 <= s.length <= 10^5→ A solution that tries every deletion does up to n palindrome checks of O(n) each, which is 10^10 operations for the largest input. That rules out the O(n^2) approach and pushes toward O(n).sconsists of lowercase English letters → Comparisons are plain character equality, with no case folding or skipping of non-alphanumeric characters.
Approach 1: Brute Force
Intuition
Try deleting each character one at a time and check whether the resulting string is a palindrome. If any deletion produces a palindrome, return true. A string that is already a palindrome also returns true, since deleting any one of its characters when it has matching pairs, or zero characters, still satisfies the "at most one" rule.
For each of the n possible deletions, the palindrome check is O(n), so the total work is O(n^2).
Algorithm
- For each index
ifrom0ton - 1: - Create the string with the 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.
An already-palindromic string is handled by this loop too. Deleting one character from a matching pair leaves the rest symmetric, so at least one deletion still yields a palindrome.
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 is too slow for strings up to 100,000 characters. The next approach avoids redundant deletions by only examining the one position where a deletion could matter.
Approach 2: Two Pointers (Greedy)
Intuition
Start two pointers at both ends of the string and move them inward while the mirrored characters match. At the first mismatch, the single allowed deletion has to remove either the left character or the right one, because keeping both would leave a pair that can never match. So check two substrings: s[left+1..right] (delete the left character) and s[left..right-1] (delete the right character). If either is a palindrome, the answer is true. If neither is, no single deletion can fix the string.
When the characters at the two pointers match, neither can be the deleted character without forcing the other half to absorb the deletion budget for a position that already matches. So the matching prefix and suffix are fixed, and the deletion must happen at or inside the first mismatch. That leaves only two candidates, the mismatched left character or the mismatched right character, and trying both is exhaustive. Each pointer crosses the string once, so the total work stays 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.