Valid Palindrome 2

Problem

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

Examples

Example 1:

Input:
s = "aba"
Output:
 true

Example 2:

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

Example 3:

Input:
s = "abc"
Output:
 false

Solution

Method 1 - Using Two Pointers

We can use the old approach like in [Valid Palindrome](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

Java

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)