Code Implementation

class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        result = []
        opened = 0
        for char in s:
            if char == '(':
                if opened > 0:
                    result.append(char)
                opened += 1
            else:
                opened -= 1
                if opened > 0:
                    result.append(char)
        return ''.join(result)
      

class Solution {
public:
    string removeOuterParentheses(string s) {
        string result;
        int opened = 0;
        for (char c : s) {
            if (c == '(') {
                if (opened > 0) result += c;
                opened++;
            } else {
                opened--;
                if (opened > 0) result += c;
            }
        }
        return result;
    }
};
      

class Solution {
    public String removeOuterParentheses(String s) {
        StringBuilder result = new StringBuilder();
        int opened = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                if (opened > 0) result.append(c);
                opened++;
            } else {
                opened--;
                if (opened > 0) result.append(c);
            }
        }
        return result.toString();
    }
}
      

var removeOuterParentheses = function(s) {
    let result = '';
    let opened = 0;
    for (let char of s) {
        if (char === '(') {
            if (opened > 0) result += char;
            opened++;
        } else {
            opened--;
            if (opened > 0) result += char;
        }
    }
    return result;
};
      

Problem Description

You are given a valid parentheses string s, which is composed only of the characters '(' and ')'. The string is made up of several primitive valid parentheses substrings concatenated together.

A primitive valid parentheses string is a non-empty string that cannot be split into two non-empty valid parentheses strings.

Your task is to remove the outermost parentheses of every primitive substring in s and return the resulting string.

• Each input string is valid (every opening parenthesis has a corresponding closing parenthesis).
• Do not reuse or rearrange characters; only remove the outermost parentheses from each primitive.
• There is only one valid solution for each input.

Thought Process

The first step is to recognize what "primitive" means: it's a smallest possible valid group of parentheses that can't be split into two valid groups. For example, in "(()())", we can see two primitives: "(()())" itself, or in "()()", each "()" is primitive.

The brute-force way would be to split the string into primitives, remove the first and last character from each, and join the results. But splitting into primitives could require extra space or complex logic.

Instead, we can notice that as we scan the string, the outermost parentheses of each primitive correspond to the points where the "nesting level" goes from 0 to 1 (for an opening parenthesis) and from 1 to 0 (for a closing parenthesis). If we keep a simple counter, we can tell whether a parenthesis is outermost or not.

This insight allows us to process the string in a single pass, only appending characters that are not outermost parentheses.

Solution Approach

The solution uses a counter to track the current depth of nested parentheses. Here’s a step-by-step breakdown:

1. Initialize: Set a variable (e.g., opened) to 0. This will track the current level of nesting.
2. Iterate through the string: For every character in s:
   • If the character is '(':
     • If opened is greater than 0, append '(' to the result (because it's not an outermost parenthesis).
     • Increase opened by 1.
   • If the character is ')':
     • Decrease opened by 1 first (since we're closing a parenthesis).
     • If opened is greater than 0 after decrementing, append ')' to the result (because it's not an outermost parenthesis).
3. Build the result: The result will contain all characters except the outermost parentheses of each primitive.

This approach avoids explicitly splitting the string into primitives and works efficiently in a single pass.

Example Walkthrough

Let's walk through an example with s = "(()())(())".

1. Start with opened = 0 and an empty result.
2. Read '(': opened becomes 1. Outer, so skip.
3. Read '(': opened becomes 2. Not outer, add '(' to result.
4. Read ')': opened becomes 1. Not outer, add ')' to result.
5. Read '(': opened becomes 2. Not outer, add '(' to result.
6. Read ')': opened becomes 1. Not outer, add ')' to result.
7. Read ')': opened becomes 0. Outer, so skip.
8. Read '(': opened becomes 1. Outer, so skip.
9. Read '(': opened becomes 2. Not outer, add '(' to result.
10. Read ')': opened becomes 1. Not outer, add ')' to result.
11. Read ')': opened becomes 0. Outer, so skip.

The result is "()()()".

Time and Space Complexity

Brute-force approach: If we tried to split the string into primitives and then remove the outermost parentheses from each, it would take O(n) time for splitting and another O(n) for removing and joining, so O(n) time and O(n) space.

Optimized approach (this solution): We process each character exactly once, doing constant work per character. So the time complexity is O(n), where n is the length of the input string. The space complexity is also O(n) because we may store up to n-2 characters in the output.

Summary

The key insight is that the outermost parentheses of each primitive correspond to the transitions where the nesting depth goes from 0 to 1 and back. By tracking the nesting level as we scan the string, we can efficiently identify and skip these outermost parentheses. This results in a clean and efficient O(n) solution that avoids unnecessary splitting or extra data structures.