Valid Palindrome II easy

Problem Statement

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

Example 1:

Input: s = "aba" Output: true

Example 2:

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

Steps

1. Two Pointers: Use two pointers, left and right, to traverse the string from both ends.

2. Comparison: Compare the characters at left and right.

3. Match: If the characters match, move both pointers towards the center.

4. Mismatch: If the characters do not match, we have two options:

   • Delete the character at left and recursively check if the remaining string is a palindrome.
   • Delete the character at right and recursively check if the remaining string is a palindrome. If either of these recursive calls returns true, the original string can be made a palindrome by deleting at most one character.

5. Base Case: If left becomes greater than or equal to right, it means we've reached the middle (or the string is empty/single character), indicating the string is a palindrome (or can be made a palindrome by deleting at most one character). Return true.

Explanation

The algorithm efficiently explores the possibility of deleting at most one character to make the string a palindrome. By using recursion, it avoids redundant checks. The two recursive calls explore the scenarios of removing either the left or the right mismatched character. If either scenario leads to a palindrome, the function returns true.

Code

class Solution {
    public boolean validPalindrome(String s) {
        return helper(s, 0, s.length() - 1, false);
    }

    private boolean helper(String s, int left, int right, boolean deleted) {
        if (left >= right) {
            return true;
        }

        if (s.charAt(left) == s.charAt(right)) {
            return helper(s, left + 1, right - 1, deleted);
        } else {
            if (deleted) {
                return false; // Already deleted one character, and still not a palindrome.
            } else {
                return helper(s, left + 1, right, true) || helper(s, left, right - 1, true);
            }
        }
    }
}

Complexity

• Time Complexity: O(N), where N is the length of the string. In the worst case, we might traverse the string twice (once for each recursive call when a mismatch occurs). However, the recursive calls explore non-overlapping parts of the string, so the total work is still linear.

• Space Complexity: O(N) in the worst case due to the recursive call stack. The depth of the recursion could be at most N/2 in the worst-case scenario. However, a more optimized iterative solution could bring the space complexity down to O(1).