Question

Formatted question description: https://leetcode.ca/all/1111.html

Algorithm

( ( ) ) ( )
0 1 2 3 4 5

0,3 and 4,5 are brackets at the same level, so that the depth of the two parts is 1, and the absolute value of the difference is 0

But if 0, 3 and 1, 2 are put in a group, then the depth of this part is 2, and the depth of the other part is 1, and the absolute value of the difference between the two parts is 1.

Code

    class Solution {
        public int[] maxDepthAfterSplit(String seq) {
            int n = seq.length();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                if (seq.charAt(i) == '(') {
                    // The left parenthesis of the odd layer is assigned the value 1, and the left parenthesis of the even layer is assigned the value 0
                    arr[i] = i & 1;
                } else {
                    // The index of the right parenthesis of the odd-numbered layer is an even number, and the variable needs to be assigned a value of 1; the index of the right parenthesis of the even-numbered layer is an odd number, and the change amount needs to be assigned a value of 0
                    arr[i] = (i - 1) & 1;
                }
            }
            return arr;
        }
    }


    class Solution222 {
        public int[] maxDepthAfterSplit(String seq) {
            if (seq == null || seq.isEmpty()) {
                return new int[0];
            }
            int[] res = new int[seq.length()];
            Stack<Integer> stack = new Stack<>();
            for (int i = 0; i < seq.length(); i++) {
                if (seq.charAt(i) == '(') {
                    stack.push(i);
                } else {
                    int depth = stack.size();
                    int left = stack.pop();
                    if (depth % 2 == 0) {
                        res[left] = 1;
                        res[i] = 1;
                    }
                }
            }
            return res;
        }
    }

############

class Solution {
    public int[] maxDepthAfterSplit(String seq) {
        int[] res = new int[seq.length()];
        for (int i = 0, cnt = 0; i < res.length; ++i) {
            if (seq.charAt(i) == '(') {
                res[i] = cnt++ & 1;
            } else {
                res[i] = --cnt & 1;
            }
        }
        return res;
    }
}

// OJ: https://leetcode.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    vector<int> maxDepthAfterSplit(string A) {
        int N = A.size(), lv = 0;
        vector<int> ans(N);
        for (int i = 0; i < N; ++i) {
            if (A[i] == '(') ans[i] = lv++ % 2;
            else ans[i] = --lv % 2;
        }
        return ans;
    }
};

class Solution:
    def maxDepthAfterSplit(self, seq: str) -> List[int]:
        ans = [0] * len(seq)
        a = b = 0
        for i, c in enumerate(seq):
            if c == "(":
                if a < b:
                    a += 1
                else:
                    b += 1
                    ans[i] = 1
            else:
                if a > b:
                    a -= 1
                else:
                    b -= 1
                    ans[i] = 1
        return ans

############

# 1111. Maximum Nesting Depth of Two Valid Parentheses Strings
# https://leetcode.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/

class Solution:
    def maxDepthAfterSplit(self, seq):
        A = B = 0
        res = [0] * len(seq)
        
        for i, c in enumerate(seq):
            v = 1 if c == '(' else -1
            if (v > 0) == (A < B):
                A += v
            else:
                B += v
                res[i] = 1
                
        return res

class Solution {
    public int[] maxDepthAfterSplit(String seq) {
        int length = seq.length();
        int[] depths = new int[length];
        int curDepth = -1;
        for (int i = 0; i < length; i++) {
            if (seq.charAt(i) == '(')
                depths[i] = ++curDepth;
            else
                depths[i] = curDepth--;
        }
        int[] split = new int[length];
        for (int i = 0; i < length; i++)
            split[i] = depths[i] % 2;
        return split;
    }
}

############

class Solution {
    public int[] maxDepthAfterSplit(String seq) {
        int[] res = new int[seq.length()];
        for (int i = 0, cnt = 0; i < res.length; ++i) {
            if (seq.charAt(i) == '(') {
                res[i] = cnt++ & 1;
            } else {
                res[i] = --cnt & 1;
            }
        }
        return res;
    }
}

// OJ: https://leetcode.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    vector<int> maxDepthAfterSplit(string A) {
        int N = A.size(), lv = 0;
        vector<int> ans(N);
        for (int i = 0; i < N; ++i) {
            if (A[i] == '(') ans[i] = lv++ % 2;
            else ans[i] = --lv % 2;
        }
        return ans;
    }
};

class Solution:
    def maxDepthAfterSplit(self, seq: str) -> List[int]:
        ans = [0] * len(seq)
        a = b = 0
        for i, c in enumerate(seq):
            if c == "(":
                if a < b:
                    a += 1
                else:
                    b += 1
                    ans[i] = 1
            else:
                if a > b:
                    a -= 1
                else:
                    b -= 1
                    ans[i] = 1
        return ans

############

# 1111. Maximum Nesting Depth of Two Valid Parentheses Strings
# https://leetcode.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/

class Solution:
    def maxDepthAfterSplit(self, seq):
        A = B = 0
        res = [0] * len(seq)
        
        for i, c in enumerate(seq):
            v = 1 if c == '(' else -1
            if (v > 0) == (A < B):
                A += v
            else:
                B += v
                res[i] = 1
                
        return res

1111 - Maximum Nesting Depth of Two Valid Parentheses Strings

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions