Sponsored
Sponsored
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.
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.
1var validPalindrome = function(s) {
2 let isPalindromeRange = (s, i, j) => {
3 while (i < j) {
4 if (s[i] !== s[j]) return false;
5 i++;
6 j--;
7 }
8 return true;
9 }
10 let left = 0, right = s.length - 1;
11 while (left < right) {
12 if (s[left] !== s[right]) {
13 return isPalindromeRange(s, left + 1, right) || isPalindromeRange(s, left, right - 1);
14 }
15 left++;
16 right--;
17 }
18 return true;
19};In JavaScript, we use an inner function to verify the palindrome nature of specified ranges of the string and iteratively validate the entire string.
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.
Time Complexity: O(n)
Space Complexity: O(1) by avoiding deep recursive stacks through tail optimization.
1The JavaScript solution implements the recursion strategy using an internal helper function to handle string verification and optional deletions.