Given a string s, return true if the s can be palindrome after deleting at most one character from it.
Example 1:
Input: s = "aba" Output: true
Example 2:
Input: s = "abca" Output: true Explanation: You could delete the character 'c'.
Example 3:
Input: s = "abc" Output: false
Constraints:
1 <= s.length <= 105s consists of lowercase English letters.Problem Overview: You are given a string s. The task is to determine whether it can become a palindrome after deleting at most one character. A palindrome reads the same forward and backward, so the challenge is detecting whether a single mismatch can be fixed by skipping one character.
This problem heavily relies on the two pointers pattern and careful string comparison. Instead of generating all possible deletions, you scan from both ends and react only when a mismatch appears.
Approach 1: Two Pointer Technique (O(n) time, O(1) space)
Use two pointers: left at the start of the string and right at the end. Move both pointers inward while characters match. When a mismatch appears, you get exactly one chance to delete a character. At that moment, check two possibilities: skip the left character (left + 1) or skip the right character (right - 1). If either remaining substring forms a palindrome, the answer is true.
The key insight is that only the first mismatch matters. After removing one character, the rest of the substring must already be a valid palindrome. This avoids brute-force deletion and keeps the scan linear. The algorithm performs a single pass over the string with at most one additional palindrome check, resulting in O(n) time and O(1) space. This pattern appears often in string problems that involve symmetry checks.
Approach 2: Recursive Two Pointers Method (O(n) time, O(n) recursion stack)
This variation applies the same idea but expresses the "skip one character" decision through recursion. Start with two pointers at the ends of the string. If characters match, recursively check the inner substring. When a mismatch occurs and deletion is still allowed, branch into two recursive calls: skip the left character or skip the right character.
A boolean flag tracks whether the deletion has already been used. Once the flag is consumed, further mismatches immediately fail. Although the total number of comparisons remains linear, recursive calls introduce stack usage up to O(n) space. This approach is easier to reason about conceptually because the recursive structure mirrors the palindrome definition.
Both approaches use the same core idea: a single mismatch can be corrected by removing one character. This greedy decision works because any valid solution must remove one of the two mismatching characters.
Recommended for interviews: The iterative two-pointer solution is the expected answer. It demonstrates mastery of the two pointers technique and achieves optimal O(n) time with constant space. Explaining the recursive variant can still help show deeper understanding of the decision process and the greedy nature of the first mismatch handling.
This approach uses the two-pointer technique to check if the string is a palindrome after removing at most one character. Start with two pointers at the beginning and end of the string. Move inward while the characters at these pointers are equal. If a mismatch occurs, there are two possibilities: either remove the character at the left pointer or the right pointer. If either results in a palindrome, then the string can be considered a valid palindrome after one deletion.
The solution uses helper function isPalindromeRange to check if a sub-range of the string is a palindrome. The main function, validPalindrome, attempts to verify if the string becomes a palindrome after removing one mismatched character, if any.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1) as we use a constant amount of extra space.
This approach uses recursion to accomplish the same task. When encountering the first differing pair of characters, we make two recursive calls: one ignoring the left character and one ignoring the right character. If either recursive call results in a valid palindrome, the whole string can be considered a valid palindrome after a single character deletion.
The C solution applies a helper function that manages recursive calls whenever a mismatched pair of characters is found, implementing an efficient recursive resolution.
Time Complexity: O(n)
Space Complexity: O(1) by avoiding deep recursive stacks through tail optimization.
We use two pointers to point to the left and right ends of the string, respectively. Each time, we check whether the characters pointed to by the two pointers are the same. If they are not the same, we check whether the string is a palindrome after deleting the character corresponding to the left pointer, or we check whether the string is a palindrome after deleting the character corresponding to the right pointer. If the characters pointed to by the two pointers are the same, we move both pointers towards the middle by one position, until the two pointers meet.
If we have not encountered a situation where the characters pointed to by the pointers are different by the end of the traversal, then the string itself is a palindrome, and we return true.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
JavaScript
C#
| Approach | Complexity |
|---|---|
| Two Pointer Technique | Time Complexity: O(n), where n is the length of the string. |
| Recursive Two Pointers Method | Time Complexity: O(n) |
| Two Pointers | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointer Technique | O(n) | O(1) | Best general solution. Optimal for interviews and large strings because it uses constant extra memory. |
| Recursive Two Pointers | O(n) | O(n) | Useful for conceptual clarity or when explaining the skip decision recursively. |
Valid Palindrome II - Leetcode 680 - Python • NeetCode • 77,359 views views
Watch 9 more video solutions →Practice Valid Palindrome II with our built-in code editor and test cases.
Practice on FleetCode