Parentheses Grouping Algorithm

Given a string s containing balanced parentheses “(” and “)”, split them into the maximum number of balanced groups.

Constraints
n ≤ 100,000 where n is length of s.
Example 1
Input
s = “()()(()())”
Output
[“()”, “()”, “(()())”]

Algorithm to Grouop Parentheses

Let’s keep a balance counter, and increment it (denotes how many opening brackets) when we have “(“, and decrement it when we have closing brackets. When it becomes zero, we know we can push/split the current balanced parentheses string into the result. This is greedy and optimal, as we greedily push the balanced parentheses (current found which is to be the smallest)

Python implementation to group the parentheses:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def groupParentheses(self, s):
        ans = []
        b, c = 0, ""
        for i in s:
            c += i
            if i == '(':
                b += 1
            elif i == ')':
                b -= 1
                if b == 0:
                    ans.append(c)
                    c = ""
        return ans

class Solution:
    def groupParentheses(self, s):
        ans = []
        b, c = 0, ""
        for i in s:
            c += i
            if i == '(':
                b += 1
            elif i == ')':
                b -= 1
                if b == 0:
                    ans.append(c)
                    c = ""
        return ans

And here is the C++ implementation to group the parentheses string:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

vecto<string> groupParentheses(string s) {
    int b = 0;
    vector<string> ans;
    string cur = "";
    for (auto &n: s) {
        cur += n;
        if (n == '(') {
            b ++;
        } else if (n == ')') {
            b --;
            if (b == 0) {
                ans.push_back(cur);
                cur = "";
            }
        }
    }
    return ans;
}

vecto<string> groupParentheses(string s) {
    int b = 0;
    vector<string> ans;
    string cur = "";
    for (auto &n: s) {
        cur += n;
        if (n == '(') {
            b ++;
        } else if (n == ')') {
            b --;
            if (b == 0) {
                ans.push_back(cur);
                cur = "";
            }
        }
    }
    return ans;
}

Both implementations run at O(N) time where N is the number of characters in the parentheses string. And the space complexity is O(1) constant. The algorithm is actually quite similar to other Parentheses problems (Teaching Kids Programming – Enhanced Valid Parenthese String Algorithm using a Stack) as we are using a balance counter to store the current opening brackets/parentheses.

–EOF (The Ultimate Computing & Technology Blog) —