Solution: A Naive Attempt

This is a stack practice problem, so you already know we are going to solve it with a stack. But before we write any code, let’s try to solve it without one. If we see what goes wrong without a stack, we will understand what the stack gives us.

We have three types of brackets: (), [], and {}. Each type has an opening and a closing bracket. We can write a loop that goes through the string character by character, and as soon as it sees an opening bracket, it looks for the next unmarked closing bracket of the same type. We can imagine keeping a boolean array of the same length as the string, initialized to false, to mark which characters have been matched. When we find a match, we mark both the opening and closing brackets as true. If an opening bracket finds no closing bracket, the string is invalid. At the end of the loop, the string is valid if every character is marked as true.

Let’s try this algorithm on some example inputs:

Valid: ()

Our algorithm sees the ( at index 0, looks for the next ), finds it at index 1, and marks both as true. At the end of the loop, all characters are marked as true, so the string is valid.

Valid: ()[]{}

Our algorithm sees the ( at index 0, looks for the next ), finds it at index 1, and marks both as true. Then it sees the ) at index 1, but that bracket is already marked as matched, so it goes to [ at index 2, looks for the next ], finds it at index 3, and marks both as true. Next, the algorithm goes to index 3 where it sees the ] that is already marked as matched, so it goes forward and sees the { at index 4, looks for the next }, finds it at index 5, and marks both as true. Finally, the algorithm goes to index 5 and sees the }, which is already matched. At the end of the loop, all characters are marked as true, so the string is valid.

Valid: {[()]}

Our algorithm sees the { at index 0, looks for the next }, finds it at index 5, and marks both as true. Then it sees the [ at index 1, looks for the next ], finds it at index 4, and marks both as true. Then, it sees the ( at index 2, looks for the next ), finds it at index 3, and marks both as true. The characters at indices 3, 4, and 5 are already marked as matched. At the end of the loop, all characters are marked as true, so the string is valid.

Invalid: (]

Our algorithm sees the ( at index 0 and looks for the next ), but there is no ) in the string. The ( cannot be matched, so the string is invalid.

Invalid: (()

Our algorithm sees the ( at index 0, looks for the next ), finds it at index 2, and marks both as true. Then it sees the ( at index 1 and looks for the next unmarked ), but there is none. The string is invalid.

Invalid: )(

Our algorithm only starts matches at opening brackets, so it passes over the ) at index 0. It sees the ( at index 1 and looks for a ) after it, but there is none. The string is invalid.

We could also adjust the algorithm to declare the string invalid as soon as it sees a closing bracket that has no unmarked opening bracket before it.

Invalid: ([)]

Our algorithm sees the ( at index 0 and looks for the next ). It finds it at index 2, so it marks indices 0 and 2. Then it sees the [ at index 1 and looks for the next ]. It finds it at index 3, so it marks indices 1 and 3. The characters at indices 2 and 3 are already marked as matched, so the loop is done. At the end of the loop, every character is marked as true, so the algorithm declares the string valid.

But ([)] is not valid. The [ opens inside the ( pair, so it must close before the ( does. Here the ( closes first. The brackets close in the wrong order, and our algorithm did not notice. It never looks at the characters between the opening bracket and its closing bracket, so it does not see the ordering error.

So this algorithm is incorrect.

The algorithm is also slow. Its runtime is $O(n^2)$ in the worst case, where $n$ is the length of the string: there can be about $n/2$ opening brackets, and each one may scan the rest of the string looking for its match. The auxiliary space is $O(n)$: the boolean array marking which characters have been matched has one entry per character.