Valid Parentheses

This article talks about a problem famously known as Valid Parentheses. True to its name the problem deals with finding whether a given string has valid set of parentheses. If you have been around mathematics or vice-versa 😝, then you already know what does valid parentheses mean and the importance of it. For full blown solutions you can always refer LeetCode. This article intends to just “Spot the Differences”. 🐮🐶

Problem 1

Given a string containing characters '(' and ')' determine if the input string is valid. An input string is valid if, each opening bracket has a corresponding closing bracket.

> Let’s first analyze what is a valid string.

It’s always a good practice to think about the problem before jumping on to the solution. Let’s take some examples:

Valid:
()()()
(())()
((8)()8)
(((())))
Invalid:
()(()
())(

Approach 1: Using a counter

As you might have noticed a parentheses string is valid if there is a closing bracket for every opening bracket. Also, the closing bracket should always come after the opening bracket.

This algorithm is simple:

1. Initialize a counter = 0.
2. With every opening bracket we increment the counter by 1.
3. With every closing bracket we decrement the counter by 1.
4. If at any point counter < 0, this would mean we have encountered more closing brackets than the opening ones. Hence, invalid string.
5. If in the end counter > 0, this would mean some opening brackets don’t have their counter closing counterparts. Hence, the string is invalid.
6. Otherwise, the string is valid.

Approach 2: Using a Stack

Imagine you are given some plates one by one and you are asked to stack those plates. After all, stack in data structures is analogous to a stack of plates 🙃. The plates you are given are either red in color or blue. But there is a nice twist to this exercise, whenever you encounter a red plate you have to remove the top most blue plate.

If we follow this guideline red plate is never on the stack. Rather everytime a red plate is encountered it takes out one of the blue plates from the stack.

Plates are analogous to brackets. Assume blue plate is the opening bracket and red plate is the closing bracket. In the end if the stack is empty, we would say every blue plate had a matching red plate in correct sequence.

This is exactly what we do in this algorithm. Let’s look at the steps:

1. Iterate the given string.
2. If we encounter an opening bracket i.e. '(', push it onto the stack.
3. If we encounter a closing bracket i.e. ')', then check the element on the top of the stack. If the top element is '(' then pop the top element. Else, the string is invalid.
4. In the end if the stack is empty then the given string is valid, otherwise its invalid.

Note, we use a stack for this problem because a stack has the property that the last element pushed onto the stack is the first element to be popped. This property helps to ensure when we are finding the closest opening bracket for a closing bracket it will always be on the top of the stack.

A string can be valid if inside every pair of opening and closing brackets lies a valid string of parentheses. Thus, a {substring} within a string is resolved first and then the its enclosing brackets are matched and removed. Just like the matching plates 🤓. We will talk about the stack based approach in detail for Problem 2, so jump on to the next problem.

Problem 2

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

An input string is valid if:

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

Valid Parentheses - LeetCode

Approach 1: Using a counter/counters

This approach doesn’t work for Problem 2.

Let’s look into the reason.

According to the counter based approach, whenever we encounter any of the opening brackets i.e. '(', '{', '[', we increment the counter by 1 and whenever we encounter a closing bracket i.e. ')', '}', ']'we decrement the counter by 1.

As per the diagram, the given string is { { { ). Following the counter based approach we increment the counter by 1 when we encounter opening bracket. And decrement the counter by 1 when we encounter a closing bracket. The final value of the counter turns out to be zero. But is this string valid?

The issue with this approach is that we might end up closing a round bracket with a curly bracket and still call the string as valid.

What you might be thinking is that there are three kinds brackets, may be we need three counters? One for each type, right? This would ensure sure the same kind of brackets are always valid if only compared with their own kind. But what about the relative order.

For e.g. in the string (({))} , if the round brackets are separated from the curly brackets, the round brackets in isolation would form a valid string i.e. (()). Also the curly brackets would form a valid string of {}. But, when they are together in the string (({))} it becomes invalid. Thus it’s important to account for the relative ordering of the brackets.

From the diagram above its clear why we can’t use the counter based approach when the valid parentheses problem has more than one type of brackets.

Approach 2: Using a Stack

Let’s talk about the relative order between brackets to understand how stack can be helpful especially when the brackets are of more than one kind.

Let’s repeat what we analyzed before, a string can be valid if inside every pair of opening and closing brackets lies a valid string of parentheses.

Look at how the original strings validity is based on the validity of its substrings.

Thus, from the diagram above we can say a string is valid, if every opening bracket is followed by its closing bracket but only after a valid a substring.

From this diagram, we now know a closing bracket is always matched with its nearest unmatched opening bracket on the left. This property is what makes stack the best choice for this problem.

As discussed in the diagram above, any closing bracket is matched to its nearest unmatched opening bracket on the left.

What if we remove an opening bracket on the left whenever a closing bracket is encountered.

Thus, Stack has the best use here. The last opening bracket pushed on the stack would the nearest one. Whenever a closing bracket is encountered the top most bracket on the stack should be a match.

Imagine a scenario where the given string is {(()()}}. By the time we are looking at the closing bracket which is at index 6, the brackets between 2–5 index would have already been matched and hence cleared way for the next match. Thus, a closing bracket would always find its opening bracket on the top of stack.

The steps are pretty similar to what we had for Problem 1.

The only difference is that for Problem 2 we also need to consider the kind of the bracket.

1. Iterate the given string.
2. If we encounter an opening bracket i.e. '(', '{' or '[', push it onto the stack.
3. If we encounter a closing bracket i.e. ')', '}' or ']', then check the element on the top of the stack. If the top element is the matching opening bracket, then pop the top element. Else, the string is invalid.
4. In the end if the stack is empty then the given string is valid, otherwise its invalid.

Hey ! if you liked the article, hit the clap 👏 button multiple times i.e. in the range [1, 50] 🤓💛.

Your like could help in recommending the article to others 👻