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.
    • 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 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.

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.

Example 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 variable cnt = 0.
  • Start iterating over the string:
    • First character is '(': cnt becomes 1. Since cnt is not more than 1, we do not add to ans.
    • Second character '(': cnt becomes 2. Now cnt > 1, so we add '(' to ansans = ['('].
    • Third character ')': cnt decreases to 1 but we check it before decreasing, so it was 2, add ')'ans = ['(', ')'].
    • Fourth character '(': cnt increases to 2, added to ansans = ['(', ')', '('].
    • Fifth character ')': Decrease cnt to 1, and since it was 2, 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 becomes 1 again, no addition to ans.
    • Seventh character '(': cnt increases to 2, which means it's not outer, add '('ans = ['(', ')', '(', ')', '('].
    • Eighth character ')': Decrease cnt to 1, add ')'ans = ['(', ')', '(', ')', '(', ')'].
  • 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.

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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 us n 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 takes O(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 space O(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. The ans list thus grows with the size of the input and can be considered O(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.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫