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.
1class Solution {
2 private boolean isPalindromeRange(String s, int i, int j) {
3 while (i < j) {
4 if (s.charAt(i) != s.charAt(j)) return false;
5 i++;
6 j--;
7 }
8 return true;
9 }
10 public boolean validPalindrome(String s) {
11 int left = 0;
12 int right = s.length() - 1;
13 while (left < right) {
14 if (s.charAt(left) != s.charAt(right)) {
15 return isPalindromeRange(s, left + 1, right) || isPalindromeRange(s, left, right - 1);
16 }
17 left++;
18 right--;
19 }
20 return true;
21 }
22}The Java solution uses similar logic, checking the string from both ends and verifying sub-ranges for palindromes.
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.