Problem statement

https://leetcode.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/

Solution

Let us go brackets by bracket and keep balance of two substrings. Each time we will add to the string which have smaller balance and remove from the string with larger balance.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def maxDepthAfterSplit(self, s):
        bal1, bal2, ans = 0, 0, []
        for x in s:
            if x == "(":
                if bal1 < bal2:
                    ans += [0]
                    bal1 += 1
                else:
                    ans += [1]
                    bal2 += 1
            else:
                if bal1 < bal2:
                    ans += [1]
                    bal2 -= 1
                else:
                    ans += [0]
                    bal1 -= 1                
        return ans