# 20 Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '\[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()\[]{}" are all valid but "(]" and "(\[)]" are not.

* Using a stack is a very natural solution in maintaining valid amounts of inverses.

```cpp
bool isOpening(char i) {
    return (i == '[' || i == '(' || i == '{');
}

// need explicitly b/c i need to ignore other nonsense chars
bool isClosing(char i) {
    return (i == ']' || i == ')' || i == '}');
}

bool isValid(string s) {
    stack<char> st;
    unordered_map<char, char> brackets = {
        {  ']' , '['  },{  ')' , '('  },{  '}' , '{'  }
    };

    for (auto i : s) {
        if (isOpening(i)) {
            st.push(i);
        }
        else {
            if (!st.empty() && isClosing(i) && brackets.find(i)->second == st.top()) {
                st.pop();
            }
            else if (!isClosing(i) && !isOpening(i)) continue;
            else return false;
        }
    }

    return st.empty();
}


int main(int argc, char **argv) {

    string test = "{}{}{}";
    cout << boolalpha << isValid(test) << endl;

    test = "]";
    cout << boolalpha << isValid(test) << endl;

    test = "{";
    cout << boolalpha << isValid(test) << endl;

    test = "{]fdfdfdd";
    cout << boolalpha << isValid(test) << endl;

    test = "{[}]";
    cout << boolalpha << isValid(test) << endl;

    test = "dsd{()()[]}";
    cout << boolalpha << isValid(test) << endl;
}
```

**Constant Space Solution**

* Limitations: Only works with brackets of the same type e.g. `()()` or `[]`.
* The idea is the same: I am counting the number of opening and closing parathesis types. In the end, the number of opening parathesis should match the number of closing paranthesis.&#x20;
* The check for `(counter < 0)` ensures that if a closing paranthesis ever comes before a opening, then the counter would be negative, and we cannot have that. Likewise, in the stack method.

```cpp
bool isOpening(char i) {
    return (i == '[' || i == '(' || i == '{');
} // checks opening

bool isClosing(char i) {
    return (i == ']' || i == ')' || i == '}');
} // checks closing

const unordered_set<char> allowed = {
    '[' ,']', '(' , ')','{' , '}'
}; // set of allowed parathesis types

   /*
   Uses a counter to increment or decrement the number of
   opening or closing paranthesis respectively.

   Effectively works in a similiar way using the stack
   method.
   */
bool isValid(const string &s) {
    int counter = 0;

    for (char c : s) {
        if (allowed.find(c) == allowed.end()) continue;
        if (isOpening(c)) counter++;
        else if (isClosing(c)) counter--;
        if (counter < 0) return false;
    }

    return counter == 0;
}


int main()
{
    string test;

    test = "))((";
    cout << boolalpha << isValid(test) << endl; // true

    test = "{}fdfdfdd";
    cout << boolalpha << isValid(test) << endl; // true

    test = "{}{sdsd}{}";
    cout << boolalpha << isValid(test) << endl; // true

    test = "]";
    cout << boolalpha << isValid(test) << endl; // false

    test = "{";
    cout << boolalpha << isValid(test) << endl; // false

    test = "(())";
    cout << boolalpha << isValid(test) << endl; // true

    test = "()()()(())()()(()))";
    cout << boolalpha << isValid(test) << endl; // false

    test = "(()(()))";
    cout << boolalpha << isValid(test) << endl; // true
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/20_valid_parentheses.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.