Using a Counter?

One easy solution that may come to mind is using a counter-- a simple variable that tracks the difference in opening and closing symbols. For example, consider (()). Here's a potential algorithm:

1. Setup a variable counter, initialize it to 0
2. Iterate the input string, when we see an opening (, we increment the counter by 1
3. When we see a closing ) we decrement the counter by 1
4. If counter ever drops below 0, it's invalid because we've seen more closing brackets than the opening ones
5. If counter > 0 when all is said and done, some opening braces don’t have their closing counterparts
6. Otherwise, the string is valid

This seems straightforward and simple, but it doesn't actually work for this problem!

Why is this? Well, we're dealing with multiple type of symbols. In this case, relative order matters. Consider the following:

What else can we do?