We'll solve this problem by walking left to right. It's always valid to open a new opened parenthesis ( { [, as we walk. The only time a string is invalid is if we come across a closing parenthesis ) } ] in the wrong place. To solve this problem, we need to make sure every closing parenthesis matches the most recent open parenthesis.

Here's an example of this. When we get to the 4th character, the most recent unmatched open parenthesis is (. This means the only allowed closing parenthesis is ).

To check if this holds, you want to be able to efficiently find the most recent open parenthesis. You can do this by storing all of the opened parentheses that you've seen so far in an Array called opened.

You always append parentheses to the array, which means that the most recent opened parenthesis will always be at the end of the array. This means you can always use the last entry of opened to check if the current character is valid. Here's an example, when we get to the 5th character in the below string:

Whenever you match a closed parenthesis with an open parenthesis, you should pop that open parenthesis from opened, because it's been matched.

Here's the full code to solve this problem:

This is technically a Stack problem, since we're only adding/removing elements from the end of the opened array.

Time Complexity $O(n)$. We do an $O(1)$ operation $n$ times.

Normally adding/removing elements in an array is $O(n)$. But since we're adding and removing elements from the very end of the array, all operations are $O(1)$.

Space Complexity $O(n)$. opened might grow to size $n$ if the string is all open parentheses.