1021. Remove Outermost Parentheses.md

1021. Remove Outermost Parentheses

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 = P_1 + P_2 + ... + P_k, where P_i 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: "(()())(())"
Output: "()()()"

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

Example 2:

Input: "(()())(())(()(()))"
Output: "()()()()(())"

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

Example 3:

Input: "()()"
Output: ""

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

Note:

• S.length <= 10000
• S[i] is "(" or ")"
• S is a valid parentheses string

Solution

• java

  • mine

  Runtime: 16 ms, faster than 18.33% of Java online submissions for Remove Outermost Parentheses.

  Memory Usage: 35.8 MB, less than 100.00% of Java online submissions for Remove Outermost Parentheses.

  class Solution {
      public String removeOuterParentheses(String S) {
          char[] arr = S.toCharArray();
          int s = 0;
          List<Integer> indexs = new ArrayList<>();
          for (int i = 0; i < arr.length; i++) {
              if (arr[i] == '(') {
                  s++;
              } else if (arr[i] == ')') {
                  s--;
              }
              if (indexs.size() % 2 == 0 && s == 1) {
                  indexs.add(i + 1);
              } else if (indexs.size() % 2 != 0 && s == 0) {
                  indexs.add(i);
              }
          }
          String res = "";
          for (int i = 0; i < indexs.size(); i += 2) {
              res += S.substring(indexs.get(i), indexs.get(i + 1));
          }
          return res;
      }
  }
  

  • nice

  Runtime: 2 ms, faster than 98.06% of Java online submissions for Remove Outermost Parentheses.

  Memory Usage: 35.2 MB, less than 100.00% of Java online submissions for Remove Outermost Parentheses.

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