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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(1) by avoiding deep recursive stacks through tail optimization.
| 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) |
Valid Palindrome II - Leetcode 680 - Python • NeetCode • 58,944 views views
Watch 9 more video solutions →Practice Valid Palindrome II with our built-in code editor and test cases.
Practice on FleetCode