It seems like all test cases have a right most extra letter to drop.
Test cases should contain also a left mot extra letter.
E.g.
“madamz” → right most extra letter
“zmadam”-> left most extra letter
A solution that I found is to run the algorithm twice and check if one of the two iteration produces a true value.
public class ValidPalindromeII {
public static boolean isPalindrome(String s) {
return isPalindrome(s, ValidPalindromeII.Skippable.LEFT) || isPalindrome(s, ValidPalindromeII.Skippable.RIGHT);
}
private static boolean isPalindrome(String s, Skippable sk) {
int left = 0;
int right = s.length() -1;
int counter = 0;
while (left <= right) {
while (s.charAt(left) != s.charAt(right) && left <= right) {
counter++;
if(counter > 1) {
return false;
}
if(sk == ValidPalindromeII.Skippable.LEFT) {
left++;
} else {
right--;
}
}
left++;
right--;
}
return true;
}
enum Skippable {
LEFT,
RIGHT
}
}
Anyways, I wouldn’t include this exercise in 2 pointer category.
It’s way simpler to use a hash map where when the string contains an even number of letters, the hash map size at the end should be 0, if odd it should be 1 instead.
Course: Grokking Coding Interview Patterns in Java - Learn Interactively
Lesson: https://www.educative.io/courses/grokking-coding-interview-patterns-java/qAWVrz2GkjG
