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.
1public class Solution {
2 private bool IsPalindromeRange(string s, int i, int j) {
3 while (i < j) {
4 if (s[i] != s[j]) return false;
5 i++;
6 j--;
7 }
8 return true;
9 }
10 public bool ValidPalindrome(string s) {
11 int left = 0;
12 int right = s.Length - 1;
13 while (left < right) {
14 if (s[left] != s[right]) {
15 return IsPalindromeRange(s, left + 1, right) || IsPalindromeRange(s, left, right - 1);
16 }
17 left++;
18 right--;
19 }
20 return true;
21 }
22}In this C# solution, we use similar logic to check the validity of potential palindromes by evaluating the string with and without potential mismatch characters.
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.