Valid Parentheses II
Lessons Learned: String manipulation
Question: Implement an algorithm to print all valid (properly opened and closed) combinations of n pairs of parentheses.
Example:
Input: 3
Output:
((())), (()()), ()(()), ()()()
Solution
Approach 1: Slow, Working
What we could do as a first take on the solution is to start with what we would have for valid combinations of n-1 pairs, and see how we would come up with n pairs from this.
Let’s take the solution we have which is n = 3:
((())), (()()), ()(()), ()()()
How can we derive this solution from n = 2? Solution to n = 2 is:
(()) ()()
We can approach this by just adding parentheses at every possible location for both options we have for n = 2. Note that we don’t add parentheses to the end of the string, since this results in duplicate parens.
Case (()):
(()())(insert pair after first left parentheses)
(()())(insert pair after second left parentheses)
()(())(insert pair at beginning of string)
Case ()():
(())()(insert pair after first left parentheses)
()(())(insert pair after second left parentheses)
()()()(insert pair at beginning of string)
As you’ll notice we still have a duplicate parentheses, ()(()). We’ll have to filter out duplicates in this approach:
Approach 2: Fast, Working
The above solution is correct, but is a bit inefficient in that it creates duplicate parens that we have to go back and filter.
We can fix this issue by starting to build the string from scratch rather than looking at the n - 1 values. As long as our parentheses stay valid, we can come up with new parentheses values by adding left and right parens.
For each index of the string that we generate, we have to decide whether to add a right or left parens to the string. How do we know if we can add either a right or a left parens?
Left Parens: Simply add a left parens if there are left parens remaining. No other condition for left parens.
Right Parens: We can add a right parens as long as it will not lead to an invalid parentheses. This will occur if and only if there are more right parens than left parens. Ex: (()))
As long as we keep track of the remaining left parens and remaining right parens, we can add either one and make a recursive call to add the next character. Using the above guidelines, if there are left parens remaining, we add a left parens and recurse. If there are more right parens remaining than left (meaning more left than right in the solution so far), then we add a right parens and recurse.
We’re guaranteed the generated string is unique, since we are adding left and right parens at each index in the string.
We’re done!
Interested in breaking into Computer Science? Eager to expand your knowledge base and learn new things? Enjoy problem solving? If so, this newsletter is for you. Subscribe to get fully explained interview prompts commonly given in engineering interviews, from Arrays to Dynamic Programming. Questions come out weekly and are also categorized by subject and difficulty.
Subscribe to get full access to the newsletter. Never miss an update.