Greedy: Given a string, check if it is a valid parenthesis or not

Problem Statement:

You are given a string having only “(“, “)”, “*”. Return true if its a valid parenthesis.

* can be treated as single right parenthesis or a single left parenthesis or an empty string.

Example:

Input: str = "(*)"

Output: True

Solution Explanation:

We will solve the problem using greedy approach.

Take 2 variables, low and high.

When you encounter “(” increment both counter by 1

if “)” decrement low and high by 1.

If “*” decrement low by 1 and increment high by 1.

If high become -ve, then return false.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

bool solution(string s) 
{
    int low = 0, high = 0;

    for (char c : s) 
    {
        if (c == '(') 
        {
            low++;
            high++;
        } 
        else if (c == ')') 
        {
            low--;
            high--;
        } 
        else 
        {
            low--;
            high++;
        }

        if (high < 0) 
        	return false;

        if (low < 0) 
        	low = 0;
    }
    
    return 
    	low == 0;
}


int main() 
{
    string str = "aba";

    cout <<solution(str);
}

Output

1