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.
1 public bool ValidPalindrome(string s) {
return Helper(s, 0, s.Length - 1, false);
}
private bool Helper(string s, int left, int right, bool deleted) {
while (left < right) {
if (s[left] != s[right]) {
if (deleted) return false;
return Helper(s, left + 1, right, true) || Helper(s, left, right - 1, true);
}
left++;
right--;
}
return true;
}
}This C# version implements a recursive function approach, mirroring solutions in other languages but optimizes tail recursion where applicable.