Remove Outermost Parentheses
This problem can be approached by using a stack-based solution. A counter is used to keep track of the balance of the parentheses. When we see an opening bracket, we increase the counter, and when we see a closing bracket, we decrease the counter. If we find a closing bracket and the counter is 1, we know that we’ve found a primitive string. If we find an opening bracket and the counter is not 0, we know we are not at the outermost level, so we add the parentheses to our result.
Python solution:
|
|
This code iterates over each character in the string s
. If the character is ‘(’, it increments the counter and adds it to the result string if it’s not an outermost ‘(’. If the character is ‘)’, it decrements the counter and adds it to the result string if it’s not an outermost ‘)’. After all the iterations, the result string will contain the required parentheses string with all the outermost parentheses removed.
This is a counting problem that needs to track the parenthesis somehow?
Yes, you’re correct. This problem essentially involves counting the open and close parentheses to track the “depth” of the parentheses. If you visualize the parentheses as a sort of hierarchy or tree structure, the outermost parentheses are at the “top level”, or depth zero.
We start with a counter set to 0, representing the top level. Each time we encounter an open parenthesis, we “descend” one level deeper, and each time we encounter a close parenthesis, we “ascend” one level. If we are at a level greater than zero and we encounter a parenthesis (open or close), we know it’s not an outermost parenthesis, so we add it to our result.
By using this counter to keep track of our depth within the parentheses structure, we can identify and ignore the outermost parentheses, solving the problem.
Let’s consider the first example from the problem statement:
s = “(()())(())”
Start with an empty string result and a counter at 0.
Iterate over each character in the string:
- ‘(’: counter = 1 (since counter is not greater than 0, we don’t add this to the result)
- ‘(’: counter = 2 (add this to result, as it’s not an outer parenthesis)
- ‘)’: counter = 1 (add this to result, as it’s not an outer parenthesis)
- ‘(’: counter = 2 (add this to result, as it’s not an outer parenthesis)
- ‘)’: counter = 1 (add this to result, as it’s not an outer parenthesis)
- ‘)’: counter = 0 (since counter is not greater than 0, we don’t add this to the result)
- ‘(’: counter = 1 (since counter is not greater than 0, we don’t add this to the result)
- ‘(’: counter = 2 (add this to result, as it’s not an outer parenthesis)
- ‘)’: counter = 1 (add this to result, as it’s not an outer parenthesis)
- ‘)’: counter = 0 (since counter is not greater than 0, we don’t add this to the result)
The result string is “()()()”, which is the string s with the outermost parentheses removed.
Presenting the steps in a table can help clarify the process:
Input Character | Counter Value | Action | Result |
---|---|---|---|
( | 1 | No addition (outer parenthesis) | |
( | 2 | Add to result | ( |
) | 1 | Add to result | () |
( | 2 | Add to result | ()( |
) | 1 | Add to result | ()() |
) | 0 | No addition (outer parenthesis) | ()() |
( | 1 | No addition (outer parenthesis) | ()() |
( | 2 | Add to result | ()()( |
) | 1 | Add to result | ()()() |
) | 0 | No addition (outer parenthesis) | ()()() |
In the end, the result is “()()()” which is the original string with outermost parentheses removed.
Alternative Solution
|
|
In this class, removeOuterParentheses
is a method that takes an input string of parentheses and returns a new string with the outermost parentheses removed from each primitive string in the input. It uses a list res
to hold the characters of the resulting string and a variable opened
to keep track of the balance of the parentheses. It iterates over each character in the input string, adding the character to res
only if it is not an outer parenthesis. Finally, it returns the joined string from the list res
.
This function removes the outermost parentheses of every primitive string in the parentheses string S by keeping track of the number of opened parentheses. When it encounters a ‘(’ character, it increments the counter, and when it encounters a ‘)’ character, it decrements the counter. The characters are only added to the result list if they are not outermost parentheses. At the end, the list of characters is joined into a string and returned.
The Python function, removeOuterParentheses
, removes the outermost parentheses from every primitive string in the parenthesis string s
, and returns the resulting string. A primitive string is a non-empty string that is balanced (i.e., has an equal number of matching opening and closing parentheses) and cannot be divided into two non-empty balanced strings.
Here’s how the function works:
It initializes an empty list
res
to store the characters of the resulting string, and a counteropened
to keep track of the balance of parentheses.It then iterates over each character
c
in the strings
.If
c
is an opening parenthesis andopened
is greater than 0, this meansc
is not part of the outermost parentheses, so it appendsc
tores
.If
c
is a closing parenthesis andopened
is greater than 1, this also meansc
is not part of the outermost parentheses, so it appendsc
tores
.It then updates
opened
based on whetherc
is an opening or closing parenthesis. Ifc
is an opening parenthesis,opened
is incremented by 1; ifc
is a closing parenthesis,opened
is decremented by 1.Finally, the function joins the characters in
res
together into a string and returns this string.
So, for example, if the input string s
is "(()())(())"
, the function will return "()()()"
. If s
is "(()())(())(()(()))"
, it will return "()()()()(())"
.
The time complexity of this function is O(n), where n is the length of the string s
, because each character in s
is processed once. The space complexity is also O(n), because in the worst case, the function might store all characters of s
in res
.
The opened
variable in this solution serves as a counter. It counts the number of opened parentheses we’ve encountered while traversing the string s
. This counter helps us distinguish the “outermost” parentheses from those that are not.
Here is a more detailed explanation:
- The
opened
counter starts from 0 because initially, we haven’t encountered any parentheses. - When we encounter an opening parenthesis
'('
, we first check ifopened
is greater than 0. If it is, we know this isn’t an outermost parenthesis, so we add it to our result listres
. Then, we incrementopened
by 1. - When we encounter a closing parenthesis
')'
, we check ifopened
is greater than 1. If it is, this isn’t an outermost parenthesis, so we add it tores
. Then, we decrementopened
by 1.
Through this process, we’re effectively “ignoring” the outermost parentheses, only adding those that aren’t the outermost to our result. This gives us the desired result - the string s
with all outermost parentheses removed.