# Questions

An input string is valid if:

- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.

```
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
```

**Implementation: ValidParens**

As we encounter a closing bracket, the whole string is valid iff there was an open bracket of the same type that came before it. Now, since there can be nested brackets like `(((())))`

, we need to somehow keep track of the order these open brackets appeared. However, the order if accessing them is opposite (*to the order of writing them*). Thus, a stack could be used here.

So the algorithm is:

- When we encounter an open bracket, we put it in the stack.
- When we encounter a closing bracket, we check the stack for:
2.1 if the top element is of different type, the string is invalid.
2.2 if there are no elements in the stack, the string is invalid.
- Otherwise, we move on.
- An edge condition could be if there's only open brackets, so at the end we should check if the stack size is 0. If not, the string is invalid.

### Time complexity

`O(n)`

### Space complexity

`O(n)`

Return to Index