Valid Palindrome II
Tags:
AlgorithmsStrings
Introduction
Given a string s
true
s
Example 1
Input: s = "aba"
Output: true
Output: true
Example 2
Input: s = "abca"
Output: true
Explanation: You could delete the character 'c' or 'b'.
Output: true
Explanation: You could delete the character 'c' or 'b'.
Example 3
Input: s = "abc"
Output: false
Output: false
Constraints:
- 1 <= s.length <= 105
-
consists of lowercase English letters.s
Solution 1 - Using two pointers approach
In this approach, we will use two pointers start
end
s
Implementation steps:
-
We will first initialize two variables
, andstart = 0
, both points to left and right ends of the stringend = s.length() -1
, and two more variables to count characters removed on left side and right side of the strings
andcharsDeletedOnLeft
.charsDeletedOnRight
-
While
andstart
do not intersect each other, read the characters and check the followng:end
-
If characters match on both sides : Since characters on both ends are same, increment
and decrementstart
.end
-
If characters don't match on both sides :
-
First, try removing character on right side, i.e. decrement
and incrementend
by 1.charsDeletedOnRight
-
If removing right character already tried and still characters don't match, try removing character on left side,
i.e. increment
and incrementstart
by 1, but we also need to incrementcharsDeletedOnLeft
, since we have already tried removing right side character, so we have to move it back to where it was.end
-
If both of the above options are tried, i.e. removing a left character as well as a right character, and the characters dont match, then return
.false
-
First, try removing character on right side, i.e. decrement
-
If characters match on both sides : Since characters on both ends are same, increment
public class ValidPalindromeII {
static boolean validPalindrome(String s) {
int start = 0;
int end = s.length() -1;
int charsDeletedOnLeft = 0;
int charsDeletedOnRight = 0;
while(start < end) {
if(s.charAt(start) == s.charAt(end)) {
start++;
end--;
} else {
if(charsDeletedOnRight ==0) {
end--; // try removing the right side character
charsDeletedOnRight++;
} else if(charsDeletedOnLeft ==0) {
end++;// move back since we have already tried removing one character above
start++;
charsDeletedOnLeft++;
} else {
return false;
}
}
}
return true;
}
public static void main(String[] args) {
System.out.println(validPalindrome("race a car"));
System.out.println(validPalindrome(" "));
System.out.println(validPalindrome("aba"));
System.out.println(validPalindrome("abca"));
System.out.println(validPalindrome("abc"));
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n) time where n
Space complexity: O(1).
Above implementations source code can be found at