JavaScript Problem Solvers: Remove Outermost Parentheses

CASE 008: Parentheception

To go along with the last two problems we solve in this series, the problem we will attempt to tackle today is a fairly simple pattern matching exercise that has a few clever tricks up its sleeve.

It is also a problem that required a few chin strokes for me to figure out, so I felt like it would be a good idea to include it in this series.

So, let’s get solving.

THE PROBLEM

Here is a link to the problem on LeetCode

A valid parentheses string is either empty (“”), “(” + A + “)”, or A + B, where A and B are valid parentheses strings, and + represents string concatenation. For example, “”, “()”, “(())()”, and “(()(()))” are all valid parentheses strings.
A valid parentheses string S is primitive if it is nonempty, and there does not exist a way to split it into S = A+B, with A and B nonempty valid parentheses strings.
Given a valid parentheses string S, consider its primitive decomposition: S = P_1 + P_2 + … + P_k, where P_i are primitive valid parentheses strings.
Return S after removing the outermost parentheses of every primitive string in the primitive decomposition of S.
Constraints:
  S.length <= 10000
  S[i] is “(“ or “)”
  S is a valid parentheses string
Test Cases:
  (()())(())” => “()()()”
  Explanation: The input string is “(()())(())”, with primitive decomposition “(()())” + “(())”. After removing outer parentheses of each part, this is “()()” + “()” = “()()()”.
  “(()())(())(()(()))” => “()()()()(())”
  Explanation: The input string is “(()())(())(()(()))”, with primitive decomposition “(()())” + “(())” + “(()(()))”. After removing outer parentheses of each part, this is “()()” + “()” + “()(())” = “()()()()(())”.
  “()()” => “”
  Explanation: The input string is “()()”, with primitive decomposition “()” + “()”. After removing outer parentheses of each part, this is “” + “” = “”.

THE BREAK DOWN

Okay, so the problem’s explanation is throwing a lot of information at us, and I feel like it overcomplicates what it is trying to explain. Let’s try breaking the problem’s explanation into smaller pieces, as we always do, to make sure we understand what is going on here:

A valid parentheses string is either empty (“”), “(” + A + “)”, or A + B, where A and B are valid parentheses strings, and + represents string concatenation.

To start off with, we are given a definition of what a parentheses string is. With the information provided, it seems the most basic example of a valid parenthesis string is 1 left parenthesis and 1 right parenthesis combined into a string, or simply “()”.

The next example of “(” + A + “)” shows us that we can also nest parentheses as well. If A is a valid parentheses string, and “()” is also a valid parentheses string, we can substitute A with “()” and reduce the example of “(“ + A + “)” down to just “(())”

The final example of A + B shows off some more nesting. If we again replace A with “()”, we can substitute B with the first example of “(” + A + “)”, or “(())”. If A is “()” and B is “(())”, we can assume that A + B equals “()(())”, meaning “()(())” is also a valid parentheses string.

For example, “”, “()”, “(())()”, and “( () ( () ) )” are all valid parentheses strings.

These examples help clear up the definition. The important addition here is that we are given another example of “(()(()))”. But, it is just the A + B example nested within another set of parentheses. So, if we were to “reverse engineer” it: “(()(()))” could also be represented as “(” + A + B + “)”.

There is a pattern to notice here:

A valid parentheses string always has an equal number of left and right parenthesis.

For example:

“()” => 1 left parenthesis, 1 right parenthesis

“(())” => 2 left parentheses, 2 right parentheses

“()(())” => 3 left parentheses, 3 right parentheses

“(()(()))” => 4 left parentheses, 4 right parentheses

This makes sense to me.

A valid parentheses string S is primitive if it is nonempty, and there does not exist a way to split it into S = A+B, with A and B nonempty valid parentheses strings.

This feels like the most confusing part of the problem’s explanation. But all it is explaining is that a valid parentheses string can be reduced by splitting it into 2 parts (A + B), and both A and B must contain at least 1 set of parentheses. Once it can no longer be split, it is considered a primative.

Given a valid parentheses string S, consider its primitive decomposition: S = P_1 + P_2 + … + P_k, where P_i are primitive valid parentheses strings.

This might be the most unnecessary part of the problem’s explanation, and potentially starts falling into the realm of over explanation, but I am not one to look a gift horse in the mouth.

The formula of S = P_1 + P_2 + … + P_k is just a re representation of what we have been figuring out before, and could be redefined as S = A + B + … + Z, if that makes it easier to understand. P_i is just a representation for each decomposed primitive we find in a valid parentheses string. All it is explaining is how we can break up, split, or divide a deeply nested valid parentheses primitive if we need to.

Keep in mind the pattern I mentioned before of a valid parentheses string always having an equal number of left and right parentheses. We can use this pattern to decompose a deeply nested valid parentheses string into it’s primitive.

Return S after removing the outermost parentheses of every primitive string in the primitive decomposition of S.

We finally find out what we are expected to return, which is a string. We also find out that we will need to remove the outer most set of parentheses for each decomposed primitive we find in a given string.

For example if we return to our “(” + A + B + “)” or “(()(()))” example. “(()(()))” is already considered a decomposed primitive since we cannot split it into two separate parts and still have both parts be a valid parentheses string. A would equal “(()” , which is not valid, and B would equal “(()))”, which is also not valid.

Since it is already a primitive, we can remove the outermost parentheses, and return “()(())”

So in short, we need to breakdown any given input string into it’s most primitive form, and remove the outermost parentheses of every set of parentheses we find.

Simple, right? Well…kind of.

THE CONSTRAINTS

The three constraints provided for us are a little more traditional, but it is always good to break them down as well, and make sure we understand what they are constraining. We also want to look for any hints or clues that might be relevant to a potential solution:

S.length <= 10000

Normally, we expect to receive a lower and upper limit in our constraints, whether it be for a string, or elements in an array, or something. But here, we are only given an upper limit for a given input string. This immediately tells me that we are going to have to accommodate empty input strings with a length of 0.

S[i] is “(“ or “)”

This is useful as it tells us that any character in a given string will be “(” or “)”, and we will not have to worry about any other letter or special character, nor do any type checking. In the case of an input string being empty, or if a given string is “”, then S[i] simply does not exist, so we cannot apply this constraint to empty strings. This means that a given string could still be “” and is still something we will have to account for.

S is a valid parentheses string

This constraint depends on the definition of a valid parentheses string provided for us, and removes any error handling we might encounter, like if a string is “)(”, “()(())(”, or simply “)”. We do not have to worry about any mutations such as these since none of them fit the definition of a valid parentheses strings.

THE SUSPECT

I think we have spent enough time going through all of the information we have, and we can finally start figuring out a solution.

Let’s use the first test case to walk through how we can go about solving this:

“(()())(())” => “()()()”
Explanation: The input string is “(()())(())”, with primitive decomposition “(()())” + “(())”.After removing outer parentheses of each part, this is “()()” + “()” = “()()()”.

The first thing we need to do is split a given string into it’s decomposed primitives.

I am going to start with the pattern I picked up on, where valid parentheses strings will always have an equal number of parentheses. The same seems to be true for a decomposed primitive as well. Both “(()())” and “(())” have an equal number of left and right parentheses.

This tells me we can iterate through a given string and use a frequency counter to count the number of left and right parentheses we find. Once the value of both keys are equal, we can slice everything from the beginning of the string to where the iterator is, and push it into an array.

For example, if we are iterating through the first test case of “(()())(())”:

On the 1st iteration, we find “(”, add it to the frequency counter and set it’s value to 1:

i: 0
given string: “(()())(())”
characters iterated through: “(”
characters left: “()())(())”
count = { “(”: 1 }

On the 2nd iteration, we find another “(”, and add 1 to it’s value:

i: 1
given string: “(()())(())”
characters iterated through: “((”
characters left: “)())(())”
count = { “(”: 2 }

On the 3rd iteration, we then find a “)”, add it to the frequency counter and set it’s value to 1:

i: 2
given string: “(()())(())”
characters iterated through: “(()”
characters left: “())(())”
count = { “(”: 2, “)”: 1 }

On the 4th iteration, we find another “(”, and add 1 to it’s value:

i: 3
given string: “(()())(())”
characters iterated through: “(()(”
characters left: “))(())”
count = { “(”: 3, “)”: 1 }

On the 5th iteration, we find another “)”, and add 1 to it’s value:

i: 4
given string: “(()())(())”
characters iterated through: “(()()”
characters left: “)(())”
count = { “(”: 3, “)”: 2 }

And finally, on the 6th iteration, we find another “)”, and add 1 to it’s value:

i: 5
given string: “(()())(())”
characters iterated through: “(()())”
characters left: “(())”
count = { “(”: 3, “)”: 3 }

Both values in the frequency counter are now equal. This means we have found a primitive for a valid parentheses string.

Now we want to slice everything from the beginning of the string to where the iterator is, and push it into an array:

primativesArr = [“(()())”]

Next, we need to start over and look for another valid parentheses string primitive. This means we are going to have to reset our frequency counter so we can properly count the number of the parentheses for the characters in the rest of the string.

We are also going to need to keep track of where the iterator was after we found the first, or previous, valid parentheses primitive. This is so we have a reference point on where to start the next slice.

So, going back to the first test case, if we add an integer to keep track of where we sliced from, and reset the frequency counter:

i: 5
num: i + 1 or 6 (stored iterator to start the next slice of a primitive)
given string: “(()())(())”
characters iterated through: “(()())”
characters left: “(())”
count: {} (reset after finding a valid parentheses primitive)

On the 7th iteration:

i: 6
num: 6 (does not change)
given string: “(()())(())”
characters iterated through: “(()())(”
characters left: “())”
count: { “(”: 1 }

8th iteration:

i: 7
num: 6
given string: “(()())(())”
characters iterated through: “(()())((”
characters left: “))”
count: { “(”: 2 }

9th iteration:

i: 8
num: 6
given string: “(()())(())”
characters iterated through: “(()())(()”
characters left: “)”
count: { “(”: 2, “)”: 1 }

And finally, the 10th iteration:

i: 9
num: 6
given string: “(()())(())”
characters iterated through: “(()())(())”
characters left: “”
count: { “(”: 2, “)”: 2 }

Once again, both values in the frequency counter are now equal, meaning we have found another valid parentheses primitive, so we can push all of the characters from num to the end of the string into primativesArr:

primativesArr = [“(()())”, “(())”]

And we have our decomposed primitives.

All we have to do now is iterate through the primitivesArr, and remove the outermost parentheses using the slice method:

primativesArr = [“()()”, “()”]

Finally, we can join all the elements in primitivesArr and return them.

With the way we are iterating and pushing elements into primitivesArr, we don’t have to worry about empty strings. If a given input string is empty, all that will be added to the primitivesArray will be more empty strings. And once they are joined, they will be concatenated into a single empty string as well.

Whew. I think I might have over complicated things.

THE PSEUDO CODE

Since that was a lot to go through, we can write up some pseudo code before trying to put this plan into action:

THE COMMENTS

Okay. Let go through things step by step and start writing out our potential solution:

First, let’s define our removeOuterParentheses function, our frequency counter, our iterator tracker, and our primitives array:

Next, let’s setup our two for loops: a for loop to iterate through the input string, and a for in loop to iterate through our primitives array:

Now, we can focus on the logic for iterating through the given input string. Let’s add the logic for our frequency counter:

Next, let’s add an if statement that will check to see if there is an equal number of left and right parentheses:

Then, add our operations to push the valid parentheses primitives to primitivesArr, reset the frequency counter, and track where we want to slice the next valid parentheses primitive we find:

Then, we can add the logic to the for in loop that iterates through primitivesArr and slices the first and last characters of an element and re assigns them.

Finally, we can join primativesArr and return it:

If we run our solution, we should match the test case provided for us:

THE FINAL SOLUTION

Let’s take a final look at our solutions without the comments, and clean up some of our syntax:

Yay.

MISSION COMPLETE

I found this problem quite intriguing and I hope I didn’t over complicate the explanation of my solution. I felt like the way the problem was originally defined was not the best, and I wanted to make sure I solidified a good understanding of the problem before moving forward. I also wanted to go into greater detail about how my solution actually functioned as well, so I hope it was worth both of our efforts.

Once again, the blogs I write about solving LeetCode or HackerRank problems isn’t about finding the solution with the lowest time or space complexity. Their focus is on the steps taken to come to a solution.

I definitely understand my solutions won’t be the best or most efficient, but either way I hope they help you or someone else figure out a way to solve a problem you encounter on this journey we call JavaScript.

Stay safe…stay healthy…and keep fighting the good fight.

Coding Interview Questions | Skilled.dev