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 <string>
2using namespace std;
3
4class Solution {
5public:
6 bool isPalindromeRange(const string& s, int i, int j) {
7 while (i < j) {
8 if (s[i] != s[j]) return false;
9 i++;
10 j--;
11 }
12 return true;
13 }
14 bool validPalindrome(string s) {
15 int left = 0;
16 int right = s.size() - 1;
17 while (left < right) {
18 if (s[left] != s[right]) {
19 return isPalindromeRange(s, left + 1, right) || isPalindromeRange(s, left, right - 1);
20 }
21 left++;
22 right--;
23 }
24 return true;
25 }
26};This C++ solution mirrors the C implementation, utilizing a helper method to determine if the string or a subsection of it is a palindrome.
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.