Problem

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

Examples

Example 1:

1
2
3
4

Input:
s = "aba"
Output:
 true

Example 2:

1
2
3
4
5

Input:
s = "abca"
Output:
 true
Explanation: You could delete the character 'c'.

Example 3:

1
2
3
4

Input:
s = "abc"
Output:
 false

Solution

Method 1 - Using Two Pointers

We can use the old approach like in Valid Palindrome. But with some modification.

For eg. take aaaz; Now when we compare left and right values, i.e. a and z, we can see they are different. But it is fine, as 1 char can be deleted. So, should it be z OR a. So, when we remove z, we get it is as palindrome. So, we have to try out both aaa and aaz to see if they are palindrome.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public boolean validPalindrome(String s) {
	int i = 0;
	int j = s.length() - 1;
	while (i < j) {
		if (s.charAt(i) != s.charAt(j)) {
			return isPalindrome(s, i + 1, j) || isPalindrome(s, i, j - 1);
		}
		i++;
		j--;
	}
	return true;
}

private boolean isPalindrome(String s, int i, int j) {
	while (i < j) {
		if (s.charAt(i++) != s.charAt(j--)) {
			return false;
		}	
	}

	return true;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)