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.
1#include <stdbool.h>
2#include <string.h>
3
4bool isPalindromeRange(char * s, int i, int j) {
5 while (i < j) {
6 if (s[i] != s[j]) return false;
7 i++;
8 j--;
9 }
10 return true;
11}
12
13bool validPalindrome(char * s) {
14 int left = 0;
15 int right = strlen(s) - 1;
16 while (left < right) {
17 if (s[left] != s[right]) {
18 return isPalindromeRange(s, left + 1, right) || isPalindromeRange(s, left, right - 1);
19 }
20 left++;
21 right--;
22 }
23 return true;
24}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.
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 Python solution combines recursion with two-pointer strategy by implementing a recursive helper function, with optional deletions permitted.