Valid Palindrome II easy

Problem Statement

Given a string s, return true if it is a palindrome, or if it can be made a palindrome by deleting at most one character.

Example 1:

Input: s = "aba" Output: true Explanation: "aba" is already a palindrome.

Example 2:

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

Steps:

1. Check if the string is already a palindrome: If it is, return true.
2. Iterate through the string: For each character, temporarily remove it and check if the resulting string is a palindrome.
3. Return true if a palindrome is found after removing one character: Otherwise, return false.

Explanation:

The core idea is to exploit the property of palindromes. A string is a palindrome if it reads the same forwards and backward. We first check if the input string is already a palindrome. If not, we systematically remove one character at a time and check if the resulting substring is a palindrome. If we find even one such palindrome, we know that the original string can be made into a palindrome by deleting at most one character, hence we return true. If we exhaust all possibilities without finding a palindrome, we return false.

We can improve efficiency by only checking the left and right halves of the string. If we find a mismatch, we try removing either the left or the right character and check if the remaining string is a palindrome.

Code:

function validPalindrome(s: string): boolean {
    function isPalindrome(str: string): boolean {
        let left = 0;
        let right = str.length - 1;
        while (left < right) {
            if (str[left] !== str[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    let left = 0;
    let right = s.length - 1;
    while (left < right) {
        if (s[left] !== s[right]) {
            // Try removing left or right character and check if it's a palindrome
            return isPalindrome(s.substring(left + 1, right + 1)) || isPalindrome(s.substring(left, right));
        }
        left++;
        right--;
    }
    return true; // Already a palindrome
}

Complexity:

• Time Complexity: O(N), where N is the length of the string. We iterate through the string at most twice (once in the validPalindrome function and at most once more in the isPalindrome function).
• Space Complexity: O(N) in the worst case, due to the substring creation in isPalindrome. However, this could be reduced to O(1) by using two pointers instead of creating substrings. The improved solution would modify isPalindrome to take the original string and starting and ending indexes as parameters instead of a substring.