1021. Remove Outermost Parentheses
Problem Description
The problem requires us to remove the outermost parentheses from each primitive valid parentheses string within a given valid parentheses string s
. A primitive valid parentheses string is one that cannot be decomposed into two nonempty valid parentheses strings. For example, in the string "(()())(())"
, there are two primitive strings: "(()())"
and "(())"
. After removing the outermost parentheses from these substrings, they become "()()"
and "()"
respectively, so the final result is "()()()"
.
Intuition
The key to solving this problem lies in finding a way to track the boundaries of the primitive strings within the input string s
. Since a valid parentheses string is balanced, we can increment a counter for each opening parenthesis and decrement it for each closing parenthesis.
Here is how we arrive at the solution:
- We define a counter
cnt
to track the level of nesting of the parentheses. - We iterate over the characters in the input string.
- For each character:
- If it's an opening parenthesis
'('
:- We increment the counter
cnt
. - If
cnt
is more than 1, it means this'('
is not the outermost parenthesis, so we include it in the result.
- We increment the counter
- If it's a closing parenthesis
')'
:- We decrement the counter
cnt
first, because we want to check if it was greater than 1 before this closing parenthesis. - If
cnt
is still greater than 0 after decrementing, it's not the outermost parenthesis, so we include it in the result.
- We decrement the counter
- If it's an opening parenthesis
- We join all the parentheses we've added to the result list to get the final string without outermost parentheses.
By maintaining the nesting level, we ensure we only remove the outermost parentheses and keep the structure of the remaining inner valid parentheses intact.
Learn more about Stack patterns.
Solution Approach
The solution implements a simple algorithm that relies on a counter to track the level of nesting of the parentheses. Let's walk through the implementation:
1class Solution:
2 def removeOuterParentheses(self, s: str) -> str:
3 ans = [] # This list will store the characters to build the final answer.
4 cnt = 0 # This counter tracks the depth of the parentheses.
5
6 for c in s: # Iterate over all the characters in the input string.
7 if c == '(': # If the character is an opening parenthesis...
8 cnt += 1 # Increase the counter.
9 if cnt > 1: # If the counter is greater than 1...
10 ans.append(c) # ...it's not an outer parenthesis, so add it to the answer.
11 else: # If the character is a closing parenthesis...
12 cnt -= 1 # Decrease the counter first.
13 if cnt > 0: # If the counter is still greater than 0...
14 ans.append(c) # ...it's not an outer parenthesis, so add it to the answer.
15
16 return ''.join(ans) # Join all characters to get the final string.
The algorithm uses a list ans
as an auxiliary data structure for building the resulting string, which avoids the higher cost of string concatenation on each iteration.
In terms of space complexity, the solution has a space complexity of O(n)
, where n
is the length of the input string, since in the worst case, we might store almost the entire string in the ans
list (minus the outer parentheses).
In terms of time complexity, the solution runs in O(n)
time. We iterate through each character in the string exactly once, with constant time operations for each character.
The pattern used here falls under the stack pattern often seen in problems involving string manipulation or parentheses validation. However, instead of using a stack, the solution cleverly employs a counter to simulate the stack's behaviour, as we are only interested in the level of nesting and not the actual sequence of parentheses that led to that nesting level.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example using the provided solution approach. We'll take the input string "(()())(())"
as our example.
- Initialize the result list
ans = []
and a counter variablecnt = 0
. - Start iterating over the string:
- First character is
'('
:cnt
becomes1
. Sincecnt
is not more than 1, we do not add toans
. - Second character
'('
:cnt
becomes2
. Nowcnt > 1
, so we add'('
toans
→ans = ['(']
. - Third character
')'
:cnt
decreases to1
but we check it before decreasing, so it was2
, add')'
→ans = ['(', ')']
. - Fourth character
'('
:cnt
increases to2
, added toans
→ans = ['(', ')', '(']
. - Fifth character
')'
: Decreasecnt
to1
, and since it was2
, add')'
→ans = ['(', ')', '(', ')']
. - Now we reach the end of the first primitive string, and the sixth character is
'('
: This is the start of the next primitive string.cnt
becomes1
again, no addition toans
. - Seventh character
'('
:cnt
increases to2
, which means it's not outer, add'('
→ans = ['(', ')', '(', ')', '(']
. - Eighth character
')'
: Decreasecnt
to1
, add')'
→ans = ['(', ')', '(', ')', '(', ')']
.
- First character is
- Continue until the end following the same logic. As we finish iterating, we have
ans = ['(', ')', '(', ')', '(', ')']
. - Join the characters in
ans
to form the final answer.return ''.join(ans)
would result in the string"()()()"
.
This example demonstrates the efficiency of the approach at handling each character of the input string and effectively maintaining the balance of the parentheses without the need for a stack. The counter cnt
acts as a simplistic stack that keeps track of nesting levels, which helps decide whether a parenthesis is outermost or not. The final string "()()()"
is the input string without the outermost parentheses.
Solution Implementation
1class Solution:
2 def removeOuterParentheses(self, input_string: str) -> str:
3 # Initialize an empty list to store the characters of the resulting string
4 result = []
5
6 # Initialize a count variable to keep track of the balance between open and close parentheses
7 balance_count = 0
8
9 # Iterate through each character in the input string
10 for char in input_string:
11 # If the current character is an open parenthesis
12 if char == '(':
13 # Increase the balance count
14 balance_count += 1
15
16 # Add the open parenthesis to the result if it's not part of an outer pair
17 if balance_count > 1:
18 result.append(char)
19 # If the current character is a close parenthesis
20 else:
21 # Decrease the balance count
22 balance_count -= 1
23
24 # Add the close parenthesis to the result if it's not part of an outer pair
25 if balance_count > 0:
26 result.append(char)
27
28 # Join the characters in the result list to form the final string without outer parentheses
29 return ''.join(result)
30
1class Solution {
2
3 // Method to remove the outermost parentheses from every primitive string in the input string
4 public String removeOuterParentheses(String s) {
5 // StringBuilder to build the result string
6 StringBuilder result = new StringBuilder();
7
8 // Counter to keep track of the balance of parentheses
9 int parenthesesCount = 0;
10
11 // Iterate through each character of the input string
12 for (int i = 0; i < s.length(); i++) {
13 char currentChar = s.charAt(i); // Current character being processed
14
15 // If the current character is an opening parenthesis ('(')
16 if (currentChar == '(') {
17 // Increment the count. If it's not the first '(' (means it's not outer), append to result
18 if (parenthesesCount > 0) {
19 result.append(currentChar);
20 }
21 parenthesesCount++;
22 }
23 // If the current character is a closing parenthesis (')')
24 else {
25 // Decrement the count before the check to see if it's a non-outer ')'
26 parenthesesCount--;
27
28 // If the count doesn't represent the outer parenthesis, append to result
29 if (parenthesesCount > 0) {
30 result.append(currentChar);
31 }
32 }
33 // No need to handle the else case, since valid inputs only contain '(' and ')'
34 }
35
36 // Return the built string which contains no outer parentheses
37 return result.toString();
38 }
39}
40
1class Solution {
2public:
3 // Method to remove the outermost parentheses in each set of valid parentheses.
4 string removeOuterParentheses(string s) {
5 string result; // This will store the final answer.
6 int depth = 0; // This keeps track of the depth of the parentheses.
7
8 // Iterate over each character in the input string.
9 for (char& c : s) {
10 if (c == '(') {
11 // If the character is an opening parenthesis, increase the depth.
12 ++depth;
13 // Only add the opening parenthesis to the result if the depth is more than 1,
14 // because the first opening parenthesis is part of the outermost parentheses.
15 if (depth > 1) {
16 result.push_back(c);
17 }
18 } else {
19 // If the character is a closing parenthesis, decrease the depth first.
20 --depth;
21 // Only add the closing parenthesis to the result if the depth is not zero after decrementing,
22 // because the last closing parenthesis corresponds to the opening one that wasn't added.
23 if (depth > 0) {
24 result.push_back(c);
25 }
26 }
27 }
28 return result; // Return the final string with outermost parentheses removed.
29 }
30};
31
1// This function removes the outermost parentheses from each primitive string within the given string
2function removeOuterParentheses(s: string): string {
3 let result = ''; // Initialize an empty string to hold the result
4 let depth = 0; // This variable keeps track of the depth of the parentheses
5
6 // Loop through each character in the input string
7 for (const char of s) {
8 if (char === '(') {
9 depth++; // Increment depth for an opening parenthesis
10 if (depth !== 1) {
11 // If the depth is not 1, it is not an outer parenthesis, so append it to the result
12 result += char;
13 }
14 } else if (char === ')') {
15 depth--; // Decrement depth for a closing parenthesis
16 if (depth !== 0) {
17 // If the depth is not 0 after decrementing, it is not an outer parenthesis, so append it to the result
18 result += char;
19 }
20 }
21 }
22
23 return result; // Return the modified string without the outermost parentheses
24}
25
Time and Space Complexity
The time complexity of the provided code can be analyzed by looking at the number of operations it performs relative to the input string length n
.
- The for-loop iterates over each character of the string
s
exactly once, giving usn
iterations. - Within the for-loop, the operations consist of simple arithmetic (incrementing or decrementing the
cnt
variable) and basic conditional checks, which all run in constant time,O(1)
. - The append operation to the
ans
list takesO(1)
time for each operation due to the dynamic array implementation of Python lists.
Putting it all together, the code's main contributing factor for time complexity is the single pass through the string, giving us a time complexity of O(n)
.
Space complexity is determined by the extra space used by the program which is not part of the input space.
- The
cnt
variable uses constant spaceO(1)
. - The
ans
list is the main auxiliary space usage, which in the worst case will store all the characters of the string except the outermost parentheses. Theans
list thus grows with the size of the input and can be consideredO(n)
in the worst-case scenario.
Therefore, the space complexity of the code is O(n)
where n
is the length of the input string s
.
Learn more about how to find time and space complexity quickly using problem constraints.
Depth first search is equivalent to which of the tree traversal order?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first