Maximum Nesting Depth Of Two Valid Parentheses Strings - Leetcode Solution

Problem Statement:

A string is a valid parentheses string (denoted VPS) if and only if it consists of "(" and ")" characters only, and:

It is the empty string, or It can be written as AB (A concatenated with B), where A and B are VPS's, or It can be written as (A), where A is a VPS.

We can similarly define the nesting depth depth(S) of any VPS S as follows:

depth("") = 0 depth(A + B) = max(depth(A), depth(B)), where A and B are VPS's. depth("(" + A + ")") = 1 + depth(A), where A is a VPS. For example, "", "()()", and "()(()())" are VPS's (with nesting depths 0, 1, and 2), and ")(" and "(()" are not VPS's.

Given a VPS seq, split it into two disjoint subsequences A and B, such that A and B are VPS's (and A.length + B.length = seq.length).

Now choose any such A and B such that max(depth(A), depth(B)) is the minimum possible value.

Return an answer array (of length seq.length) that encodes such a split: answer[i] = 0 if seq[i] is part of A, else answer[i] = 1. Note that even though multiple answers may exist, you may return any of them.

Example:

Input: seq = "(()())" Output: [0,1,1,1,1,0]

Input: seq = "()(())()" Output: [0,0,0,1,1,0,1,1]

Solution:

Approach:

In the binary tree representation of the input string with parentheses as the edges and leaves as empty String or single space, it becomes evident that an optimal splitting of the input string into two VPS A and B leads to a maximal height difference of 1.

Observations:

The definition of the maximal depth of any balanced parentheses substring is based on the maximal number of valid opening parentheses minus the maximal number of valid closing parentheses of all its prefixes. The optimal splitting into two disjunct substrings A, B leads to height(A)-height(B) = 0. The difference of the opening and closing parentheses not only equals the depth of a VPS but also counts the number of opening parentheses minus the number of closing parentheses for all its prefixes and suffixes.

Steps:

We first preprocess the input parentheses sequence seq and compute for each balanced parentheses substring its maximal nesting depth split into parts d1, d2, .., dm. The length of the sequence parts[] is equal to the number of closing parentheses ")" and the respective nesting depth of each balanced substring is stored in depths[]. We iterate the sequence and output either 0 or 1 for each parentheses character depending on the value of the nesting depth for the associated balanced parentheses substring.

Time Complexity:

Preprocessing the balanced parentheses substrings and associated depths[] takes O(n) time. The iteration over the input string and the output of the splitting encoding takes O(n) time. The overall time complexity is O(n) and is dominated by the preprocessing.

Space Complexity:

The balanced parentheses substrings are stored in an instance of class Sequence. The maximal depth of such sequence is limited to n/2. Therefore, the space complexity of the solution is O(n).

Code:

1