Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
Be sure that you clarify the input and output parameters of the problem:
Run through a set of example cases:
HAPPY CASE
Input: "aba"
Output: True
Input: s = "abc"
Output: false
EDGE CASE
Input: "abca"
Output: True
Explanation: You could delete the character 'c'.Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
Plan the solution with appropriate visualizations and pseudocode.
General Idea: We try to check the comparison of head & tail elements of the string, if they are identical characters, check the next pair, otherwise we recursively try the next two possibilities, skip one character from the left or skip one character from the right
1. Write a recursive function to handle two pointer solution while maintaining the count
2. Set the basecase if the number of available skips is below 1, return false
3. Now move the start pointer to right so it points to a alphanumeric character. Similarly move end pointer to left so it also points to a alphanumeric character.
4. Now check if both the characters are same or not (ignoring cases):
- If it is not equal then we know string is not a valid palindrome, hence return two possibilities skip one character on the left or skip one or skip one character on the right. (be sure to reduce the number of available skips by 1)
- Else continue to next iteration and repeat the same process of moving both pointers to point to next alphanumeric character till start<end.
5. After loop finishes, the string is said to be palindrome, hence return true.
6. Call start and end and point them with the two ends of the input string with the number of available skips to be 1.⚠️ Common Mistakes
The tricky part is, if the given string is not a palindrome, then we can delete at most one character from a string. After deleting a character we have to check whether a new string is a palindrome or not.
The idea here is to traverse a string from both the ends using two pointers. Let’s say the two variables are left and right. The initial values of left and right are 0 and string length minus one. Then run a loop and start comparing characters present at left and right index. If characters are equal then increment left pointer and decrement right pointer. If it is not equal then check whether a string is palindrome by deleting either the character present at left or right index.
Implement the code to solve the algorithm.
class Solution(object):
def validPalindrome(self, s):
# Write a recursive function to handle two pointer solution while maintaining the count
def isPalindrome(left, right, count):
# Set the basecase if the number of available skips is below 1, return false
if count > 1:
return False
# Now move the start pointer to right so it points to a alphanumeric character.
# Similarly move end pointer to left so it also points to a alphanumeric character
while left < right:
# Now check if both the characters are same or not (ignoring cases):
# If it is not equal then we know string is not a valid palindrome, hence return two possibilities
# skip one character on the left or skip one or skip one character on the right.
# (be sure to reduce the number of available skips by 1)
if s[left] != s[right]:
return isPalindrome(left+1, right, count+1) or isPalindrome(left, right-1, count+1)
# Else continue to next iteration and repeat the same process of moving both pointers to point to next alphanumeric character till start<end.
left += 1
right -= 1
# After loop finishes, the string is said to be palindrome, hence return true.
return True
# Call start and end and point them with the two ends of the input string with the number of available skips to be 1.
return isPalindrome(0, len(s)-1, 0)
class Solution {
public boolean validPalindrome(String s) {
// Call start and end and point them with the two ends of the input string with the number of available skips to be 1.
return isPalindrome(s, 0, s.length()-1, 1);
}
// Write a recursive function to handle two pointer solution while maintaining the count
public boolean isPalindrome(String str, int start, int end, int chance) {
// Set the basecase
// if the start and end cross, return true
if(start >= end) return true;
// Now move the start pointer to right so it points to a alphanumeric character.
// Similarly move end pointer to left so it also points to a alphanumeric character
if(str.charAt(start) == str.charAt(end))
return isPalindrome(str, start+1, end-1, chance);
// if the number of available skips is below 1, return false
if(chance == 0) return false;
// If it is not equal then we know string is not a valid palindrome, hence return two possibilities
// skip one character on the left or skip one or skip one character on the right.
// (be sure to reduce the number of available skips by 1)
return isPalindrome(str, start+1, end, chance-1) || isPalindrome(str, start, end - 1,chance-1);
}
}Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
