# Remove Outermost Parentheses
**Difficulty:** EASY
[External](https://leetcode.com/problems/remove-outermost-parentheses)
Canonical: https://scaleengineer.com/dsa/problems/remove-outermost-parentheses
**Data structures:** String, Stack
---
## Problem
A valid parentheses string is either empty `""`, `"(" + A + ")"`, or `A + B`, where `A` and `B` are valid parentheses strings, and `+` represents string concatenation.

* For example, `""`, `"()"`, `"(())()"`, and `"(()(()))"` are all valid parentheses strings.

A valid parentheses string `s` is primitive if it is nonempty, and there does not exist a way to split it into `s = A + B`, with `A` and `B` nonempty valid parentheses strings.

Given a valid parentheses string `s`, consider its primitive decomposition: `s = P1 + P2 + ... + Pk`, where `Pi` are primitive valid parentheses strings.

Return `s` _after removing the outermost parentheses of every primitive string in the primitive decomposition of_ `s`.

**Example 1:**

**Input:** s = "(()())(())"
**Output:** "()()()"
**Explanation:** 
The input string is "(()())(())", with primitive decomposition "(()())" + "(())".
After removing outer parentheses of each part, this is "()()" + "()" = "()()()".

**Example 2:**

**Input:** s = "(()())(())(()(()))"
**Output:** "()()()()(())"
**Explanation:** 
The input string is "(()())(())(()(()))", with primitive decomposition "(()())" + "(())" + "(()(()))".
After removing outer parentheses of each part, this is "()()" + "()" + "()(())" = "()()()()(())".

**Example 3:**

**Input:** s = "()()"
**Output:** ""
**Explanation:** 
The input string is "()()", with primitive decomposition "()" + "()".
After removing outer parentheses of each part, this is "" + "" = "".

**Constraints:**

* `1 <= s.length <= 105`
* `s[i]` is either `'('` or `')'`.
* `s` is a valid parentheses string.

# Approaches
## Decomposition and Rebuilding
This approach directly follows the problem's definition. It first identifies the primitive components of the input string by tracking the balance of parentheses. Once a primitive component is identified, its outermost parentheses are removed, and the inner content is appended to the result.
**Time:** O(N), where N is the length of the string. We iterate through the string once. The `substring` operation in Java takes time proportional to the length of the substring. Since the sum of lengths of all substrings is N, the total time complexity remains O(N). · **Space:** O(N), where N is the length of the input string. This is required for the `StringBuilder` that stores the result, which can have a length up to N-2.
**Pros:** The logic is a direct translation of the problem statement, making it relatively easy to understand and implement.
**Cons:** Involves creating intermediate substrings, which can be less memory-efficient and slightly slower due to object creation overhead compared to a single-pass approach.
### Explanation
We iterate through the string while maintaining a balance counter. The counter is incremented for an opening parenthesis `(` and decremented for a closing one `)`. A primitive string is a valid parentheses string that cannot be split into two non-empty valid parentheses strings. This means that for a primitive string, the balance counter only returns to zero at the very end. Therefore, whenever our balance counter, which starts at zero, returns to zero during the iteration, we have identified the end of a primitive component. We then extract this component, remove its first and last characters (the outermost parentheses), and append the remaining part to our result. We then reset the starting point for the next primitive component and continue until the entire string is processed.

```java
class Solution {
    public String removeOuterParentheses(String s) {
        StringBuilder result = new StringBuilder();
        int balance = 0;
        int start = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                balance++;
            } else {
                balance--;
            }
            if (balance == 0) {
                // Found a primitive component from start to i
                // Append the content inside the outermost parentheses
                result.append(s.substring(start + 1, i));
                // Update start for the next primitive component
                start = i + 1;
            }
        }
        return result.toString();
    }
}
```
### Algorithm
- Initialize a `StringBuilder` `result` to store the final string.
- Initialize an integer `balance = 0` to track the nesting level of parentheses.
- Initialize an integer `start = 0` to mark the beginning of the current primitive component.
- Iterate through the input string `s` from `i = 0` to `s.length() - 1`.
- If `s.charAt(i) == '('`, increment `balance`.
- If `s.charAt(i) == ')'`, decrement `balance`.
- If `balance == 0`, we have found a complete primitive component from index `start` to `i`.
- Append the inner part of this component (`s.substring(start + 1, i)`) to the `result`.
- Update `start` to `i + 1` to mark the beginning of the next component.
- After the loop, return `result.toString()`.

## Single Pass with a Counter
This is a more optimized approach that builds the result string in a single pass without explicitly decomposing the string into primitive parts. It uses a counter to determine whether a parenthesis is an outermost one and should be skipped.
**Time:** O(N), where N is the length of the string. We perform a single pass through the string, with constant time operations at each character. · **Space:** O(N) to store the `StringBuilder` for the result. In the worst case, the result string's length is close to N.
**Pros:** Highly efficient as it processes the string in a single pass.; Avoids creating intermediate substrings, reducing memory allocations and overhead.
**Cons:** The logic is slightly more abstract than the decomposition approach, as it doesn't explicitly handle primitive components.
### Explanation
The core idea is to identify which parentheses should be included in the final result. We iterate through the string, maintaining a balance counter. 

- An opening parenthesis `(` should be included if and only if it's not the *first* one in a primitive component. The first `(` of a primitive component is encountered when the balance is 0. Any subsequent `(` within that component will be encountered when the balance is greater than 0. So, we append an opening parenthesis if `balance > 0` *before* we increment the counter.

- A closing parenthesis `)` should be included if and only if it's not the *last* one in a primitive component. The last `)` of a primitive component is the one that makes the balance return to 0. Any other `)` will be encountered when the balance is greater than 1. So, we append a closing parenthesis if `balance > 0` *after* we decrement the counter.

This allows us to build the final string in one go.

```java
class Solution {
    public String removeOuterParentheses(String s) {
        StringBuilder result = new StringBuilder();
        int balance = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                if (balance > 0) {
                    result.append(c);
                }
                balance++;
            } else { // c == ')'
                balance--;
                if (balance > 0) {
                    result.append(c);
                }
            }
        }
        return result.toString();
    }
}
```
### Algorithm
- Initialize an empty `StringBuilder` `result`.
- Initialize an integer `balance = 0`.
- Iterate through each character `c` of the input string `s`.
- If `c` is `(`:
    - If `balance > 0`, append `c` to `result`.
    - Increment `balance`.
- If `c` is `)`:
    - Decrement `balance`.
    - If `balance > 0`, append `c` to `result`.
- Return `result.toString()`.

# Solutions
### Java

```java
class Solution {
public
  String removeOuterParentheses(String s) {
    StringBuilder ans = new StringBuilder();
    int cnt = 0;
    for (int i = 0; i < s.length(); ++i) {
      char c = s.charAt(i);
      if (c == '(') {
        if (++cnt > 1) {
          ans.append(c);
        }
      } else {
        if (--cnt > 0) {
          ans.append(c);
        }
      }
    }
    return ans.toString();
  }
}

```

### CPP

```cpp
class Solution {
public:
  string removeOuterParentheses(string s) {
    string ans;
    int cnt = 0;
    for (char &c : s) {
      if (c == '(') {
        if (++cnt > 1) {
          ans.push_back(c);
        }
      } else {
        if (--cnt) {
          ans.push_back(c);
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def removeOuterParentheses(self, s: str) -> str: ans = [] cnt = 0 for c in s: if c == '(': cnt += 1 if cnt > 1: ans . append(c) else: cnt -= 1 if cnt > 0: ans . append(c) return '' . join(ans)

```