Valid Palindrome II

Problem Highlights

• 🔗 Leetcode Link: Valid Palindrome II
• 💡 Problem Difficulty: Easy
• ⏰ Time to complete: 15 mins
• 🛠️ Topics: Recursion
• 🗒️ Similar Questions: Valid Palindrome, Valid Palindrome IV, Valid Palindrome III

1: U-nderstand

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:

• How do we verify if string is a palindrome of another string?
  • We compare str[i] and str[j] while iterating i++ and j–; the string is a palindrome if we never find str[i] != str[j].
• Can a string become a palindrome?
  • If str is not a palindrome, but if delete a character in string, it can become palindrome.

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'.

2: M-atch

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.

• Sort
• Two pointer solutions (left and right pointer variables): Try using two pointers technique. One pointer starts from the beginning, one starts from the end. Whenever two pointers found two unmatched characters, skip the character from either side to see if the remaining parts fits the palindrome requirement
• Storing the elements of the array in a HashMap or a Set
• Traversing the array with a sliding window

3: P-lan

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 of skips used
2. Set the basecase: if the number of skips used exceeds 1, return false
3. Loop while the start pointer is to the left of the end pointer.
4. Now check if both the characters are same or not:
- If it is not equal then we know string is not a valid palindrome as-is, hence return two possibilities: skip one character on the left or skip one character on the right. (be sure to increase the number of skips used by 1)
- Else continue to next iteration and repeat the same process of moving both pointers inward till start<end.
5. After loop finishes, the string is said to be palindrome, hence return true.
6. Call the recursive function with the pointers at the two ends of the input string and the number of skips used starting at 0.

⚠️ 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.

4: I-mplement

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 of skips used
        def isPalindrome(left, right, count):
            # Set the basecase: if the number of skips used exceeds 1, return false
            if count > 1:
                return False
            
            # Loop while the start pointer is to the left of the end pointer
            while left < right:

                # Now check if both the characters are same or not:
                # If it is not equal then we know string is not a valid palindrome as-is, hence return two possibilities: 
                # skip one character on the left or skip one character on the right. 
		# (be sure to increase the number of skips used 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 inward till start<end.
                left += 1
                right -= 1
            
	    # After loop finishes, the string is said to be palindrome, hence return true.
            return True

        # Call the recursive function with the pointers at the two ends of the input string and the number of skips used starting at 0.                       
        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;

            // If the characters at start and end match, move both pointers inward
            if(str.charAt(start) == str.charAt(end))
                return isPalindrome(str, start+1, end-1, chance);
            
            // if there are no available skips left, return false
            if(chance == 0) return false;
            
            // If it is not equal then we know string is not a valid palindrome as-is, hence return two possibilities: 
            // skip one character on the left 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);
    }
}

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code’s variables along the way.

• Trace through your code with an input to check for the expected output
• Catch possible edge cases and off-by-one errors

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

• Time Complexity: O(N) because we will run the algorithm at most twice due to a single skip. (N being the number of characters in the string)
  • However, if we had more number of skips like 4, then we will have O(N * 2^M) M being the number of skips available, because each time we skip we will have to double the number of possible strings to check.
  • Here, we have O(N * 2^1), which is O(N*2), which is basically O(N).
• Space Complexity: O(1) for the Python version because it iterates with two pointers and its recursion depth is bounded by a constant (at most one skip on each side). The Java version recurses once per matched pair of characters, so its call stack is O(N).