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. Check if the string is already a palindrome: If it is, return true immediately.

2. Iterate through the string: Compare characters from the beginning and end, moving inwards.

3. Handle Mismatches: If a mismatch is found:

   • Try deleting the character from the beginning and check if the remaining substring is a palindrome.
   • Try deleting the character from the end and check if the remaining substring is a palindrome.
   • If either of these results in a palindrome, return true.

4. Return false: If no palindrome can be formed by deleting at most one character, return false.

Explanation

The core idea is to efficiently check if a palindrome can be achieved by removing at most one character. Instead of brute-forcing all possible deletions, we cleverly handle mismatches by checking only two possibilities: deleting the character at the beginning or the end. This significantly reduces the complexity from exponential to linear.

The isPalindrome helper function provides a clear and concise way to check if a given substring is a palindrome.

Code

#include <string>

class Solution {
public:
    bool isPalindrome(const std::string& s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    bool validPalindrome(std::string s) {
        int left = 0;
        int right = s.length() - 1;

        while (left < right) {
            if (s[left] != s[right]) {
                //Try deleting from left
                std::string s1 = s.substr(left + 1, right - left);
                if (isPalindrome(s1)) return true;
                
                //Try deleting from right
                std::string s2 = s.substr(left, right - left);
                if (isPalindrome(s2)) return true;
                
                return false; //Neither deletion worked
            }
            left++;
            right--;
        }
        return true; // Already a palindrome
    }
};

Complexity

• Time Complexity: O(N), where N is the length of the string. The while loop iterates through the string at most once. The isPalindrome function also takes linear time. In the worst case, we might call isPalindrome twice, but the total time complexity remains linear.

• Space Complexity: O(N) in the worst case, due to the creation of substring s1 and s2. However, we could optimize this by avoiding substring creation and using two-pointer approach within the validPalindrome function itself. A space-optimized version would have O(1) space complexity.