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
The C solution applies a helper function that manages recursive calls whenever a mismatched pair of characters is found, implementing an efficient recursive resolution.