algoadvance

Leetcode 680. Valid Palindrome II

Problem Statement

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

Clarifying Questions

  1. What is a palindrome?
    • A string that reads the same backward as forward.
  2. Is the input string guaranteed to be non-empty?
    • Yes, the input string s will have at least one character.
  3. What characters can s contain?
    • The string s will consist only of lowercase English letters.

Strategy

To determine if a string can be a palindrome after deleting at most one character, we can use a two-pointer approach:

  1. Initialize two pointers, one at the beginning (left) and one at the end (right) of the string.
  2. Iterate through the string while comparing characters at left and right pointers.
    • If characters at both pointers are equal, move the left pointer to the right and the right pointer to the left.
    • If characters are not equal, you can either remove the character at the left or right pointer and check if the remaining substring (excluding the character) is a palindrome.

To check if a substring is a palindrome, you can write a helper function that performs this check by using a similar two-pointer technique.

Code

#include <iostream>
#include <string>
using namespace std;

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

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

        while (left < right) {
            if (s[left] == s[right]) {
                left++;
                right--;
            } else {
                // Try removing either the left or the right character
                return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
            }
        }
    
        return true;
    }
};

// Example usage
int main() {
    Solution solution;
    string s = "abca";
    
    if (solution.validPalindrome(s)) {
        cout << "The string can be a palindrome after deleting at most one character." << endl;
    } else {
        cout << "The string cannot be a palindrome after deleting at most one character." << endl;
    }

    return 0;
}

Time Complexity

  1. Time Complexity:
    • The main check loops through the string once (O(n)).
    • The helper function to check if a substring is a palindrome also takes linear time (O(n)).
    • In the worst-case scenario, we might call the helper function twice for each mismatch, resulting in O(n) + O(n), which simplifies to O(n) overall.
  2. Space Complexity:
    • The additional space used by the algorithm is O(1) since we only use a few extra variables for the pointers.

Thus, the final time complexity is O(n) and the space complexity is O(1).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI