Welcome to Subscribe On Youtube

1021. Remove Outermost Parentheses

Description

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.

Solutions

Solution 1: Direct Implementation

Traverse the string and when encountering the left bracket '(', the counter increases by one. If the counter is not $1$, it means that the current bracket is not the outermost bracket, and it is added to the result string. When the right bracket ')' is encountered, the counter is decremented by one. When the counter is not $0$, it means that the current bracket is not the outermost bracket, and it is added to the result string.

Time complexity $O(n)$, where $n$ is the string length. Ignoring the space overhead of the answer string, the space complexity is $O(1)$.

Solution 2

This implementation follows the required operations directly. It traverses the relevant values and updates its state as each value is processed. After all required states have been considered, the maintained result is returned.

• Java
• C++
• Python
• Go
• TypeScript
• Rust

• 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();
      }
  }
  
  
  // Solution 2
  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 == '(') {
                  ++cnt;
              }
              if (cnt > 1) {
                  ans.append(c);
              }
              if (c == ')') {
                  --cnt;
              }
          }
          return ans.toString();
      }
  }
  
  

• 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;
      }
  };
  
  
  // Solution 2
  class Solution {
  public:
      string removeOuterParentheses(string s) {
          string ans;
          int cnt = 0;
          for (char& c : s) {
              if (c == '(') {
                  ++cnt;
              }
              if (cnt > 1) {
                  ans.push_back(c);
              }
              if (c == ')') {
                  --cnt;
              }
          }
          return ans;
      }
  };
  
  

• 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)
  
  
  # Solution 2
  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)
              if c == ')':
                  cnt -= 1
          return ''.join(ans)
  
  

• func removeOuterParentheses(s string) string {
  	ans := []rune{}
  	cnt := 0
  	for _, c := range s {
  		if c == '(' {
  			cnt++
  			if cnt > 1 {
  				ans = append(ans, c)
  			}
  		} else {
  			cnt--
  			if cnt > 0 {
  				ans = append(ans, c)
  			}
  		}
  	}
  	return string(ans)
  }
  
  
  // Solution 2
  func removeOuterParentheses(s string) string {
  	ans := []rune{}
  	cnt := 0
  	for _, c := range s {
  		if c == '(' {
  			cnt++
  		}
  		if cnt > 1 {
  			ans = append(ans, c)
  		}
  		if c == ')' {
  			cnt--
  		}
  	}
  	return string(ans)
  }
  
  

• function removeOuterParentheses(s: string): string {
      let res = '';
      let depth = 0;
      for (const c of s) {
          if (c === '(') {
              depth++;
          }
          if (depth !== 1) {
              res += c;
          }
          if (c === ')') {
              depth--;
          }
      }
      return res;
  }
  
  

• impl Solution {
      pub fn remove_outer_parentheses(s: String) -> String {
          let mut res = String::new();
          let mut depth = 0;
          for c in s.chars() {
              if c == '(' {
                  depth += 1;
              }
              if depth != 1 {
                  res.push(c);
              }
              if c == ')' {
                  depth -= 1;
              }
          }
          res
      }
  }
  
  

All Problems

All Solutions