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

Tracking the Depth of the Parenthesses

Given the lengthy description, however, the solution is very intuitive/straightforward, i.e. keeping tracks of the depths and ignoring the first level.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    string removeOuterParentheses(string S) {
        string r = "", cur = "";
        int depth = 0;
        for (int i = 0; i < S.size(); ++ i) {
            if (S[i] == '(') {
                depth ++;
                if (depth > 1) {
                    cur += "(";
                }
            } else {
                depth --;
                if (depth == 0) {
                    r += cur;
                    cur = "";
                } else {
                    cur += ")";
                }
            }
        } 
        return r;
    }
};

class Solution {
public:
    string removeOuterParentheses(string S) {
        string r = "", cur = "";
        int depth = 0;
        for (int i = 0; i < S.size(); ++ i) {
            if (S[i] == '(') {
                depth ++;
                if (depth > 1) {
                    cur += "(";
                }
            } else {
                depth --;
                if (depth == 0) {
                    r += cur;
                    cur = "";
                } else {
                    cur += ")";
                }
            }
        } 
        return r;
    }
};

When we meet a left parenthess, we increment the depth, otherwise we decrement the depth i.e. for right parenthess. When the depth is zero for ‘)’, we need to concatenate the inner parenthesses and reset the parenthesses string. The space complexity is O(1) constant and the time complexity for above C++ implementation is O(N) where N is the length of the given input, i.e. a valid parenthesses string.

–EOF (The Ultimate Computing & Technology Blog) —