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

Java

  • 
        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;
            }
        }
    
  • // 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;
        }
    };
    
  • # 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
    
    

Java

  • 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;
        }
    }
    
  • // 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;
        }
    };
    
  • # 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
    
    

All Problems

All Solutions