algoadvance

Leetcode 678. Valid Parenthesis String

Problem Statement

1. Valid Parenthesis String:

Given a string s containing only three types of characters: '(', ')', and '*', write a function to check whether the string is valid. The string is valid if:

1. Any left parenthesis '(' must have a corresponding right parenthesis ')'.
2. Any right parenthesis ')' must have a corresponding left parenthesis '('.
3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.
4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.

Clarifying Questions

1. Can the input string be empty?
   • Yes, an empty string should be considered valid.
2. What should be returned?
   • Return true if the string is valid, otherwise return false.

Strategy

To solve this problem, we’ll use a greedy technique to keep track of the minimum and maximum possible number of open brackets at any point in the string.

• We will use two counters:
  • min_open: Tracks the minimum number of unmatched ‘(‘ considering ‘*’ can potentially act as ‘)’.
  • max_open: Tracks the maximum number of unmatched ‘(‘ considering ‘*’ can potentially act as ‘(‘.

Code

Here is the C++ code to solve the problem:

#include <iostream>
#include <string>

class Solution {
public:
    bool checkValidString(std::string s) {
        int min_open = 0;  // Minimum possible open brackets
        int max_open = 0;  // Maximum possible open brackets

        for (auto &ch : s) {
            if (ch == '(') {
                min_open++;
                max_open++;
            } else if (ch == ')') {
                min_open = std::max(min_open - 1, 0);
                max_open--;
            } else {  // '*' can be '(' or ')' or empty
                min_open = std::max(min_open - 1, 0);
                max_open++;
            }

            if (max_open < 0) {
                // This means the string can't be valid because we have more closing brackets than opening ones.
                return false;
            }
        }

        // At the end of the string, min_open must be zero for the string to be valid.
        return min_open == 0;
    }
};

// Example usage:
int main() {
    Solution sol;
    std::string s = "(*))";
    bool result = sol.checkValidString(s);
    std::cout << (result ? "Valid" : "Invalid") << std::endl;
    return 0;
}

Explanation & Time Complexity

Explanation:

1. Loop through each character in the string:
   • If it is ‘(‘, increment both min_open and max_open.
   • If it is ‘)’, decrement max_open and increment min_open unless min_open is already zero.
   • If it is ‘*’, decrement min_open (unless it’s zero) and increment max_open.
2. If max_open becomes less than 0 at any point, return false because it means there are unmatched closing brackets.
3. After processing the entire string, min_open must be zero to ensure all open brackets are matched properly. Return min_open == 0.

Time Complexity:

• The time complexity of this solution is O(n), where n is the length of the input string s. This is because we process each character of the string exactly once.
• The space complexity is O(1), as we only use a few integer variables to keep track of the state.

This approach ensures that we efficiently check the validity of the string in linear time with constant space.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?