Maximum Nesting Depth of Two Valid Parentheses Strings

Maximum Nesting Depth of Two Valid Parentheses Strings - Problem

String Stack Medium

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 ")(", "(()" 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 choice of A and B: answer[i] = 0 if seq[i] is part of A, else answer[i] = 1.

Input & Output

Example 1 — Balanced Distribution

$ Input: seq = "(()())"

› Output: [0,1,1,0,1,0]

💡 Note: Split into A="()()" (depth 1) and B="()" (depth 1). The maximum depth is min(1,1) = 1, which is optimal.

Example 2 — Simple Case

$ Input: seq = "()(())"

› Output: [0,0,1,1,1,1]

💡 Note: Split into A="()" (depth 1) and B="()()" (depth 1). Both have depth 1, giving maximum depth of 1.

Example 3 — Nested Structure

$ Input: seq = "(((())))"

› Output: [0,1,0,1,1,0,1,0]

💡 Note: Alternating assignment distributes nested levels evenly: A="(())" (depth 2) and B="(())" (depth 2), max depth = 2.

Constraints

1 ≤ seq.length ≤ 10⁴
seq is a valid parentheses string

Visualization

Tap to expand

Understanding the Visualization

Input

Valid parentheses string like "(()())"

Split Strategy

Alternate assignment based on nesting depth

Output

Array indicating group assignment for each character

Key Takeaway

🎯 Key Insight: Alternating assignment based on nesting depth parity distributes the load evenly between two groups

Asked in

G Google 25 f Facebook 20 a Amazon 15

The key insight is that to minimize the maximum depth, we need to distribute parentheses alternately between two groups based on their nesting level. The optimal approach uses depth tracking with parity-based assignment. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Stack-Based Depth Tracking	O(n)	O(1)	Track nesting depth and alternate assignment to minimize maximum depth
Brute Force - Try All Splits	O(2^n)	O(n)	Generate all possible splits and find the one with minimum maximum depth

Stack-Based Depth Tracking — Algorithm Steps

Iterate through each character
For '(': assign based on current depth parity, increment depth
For ')': decrement depth first, then assign based on new depth parity
Alternate between 0 and 1 at each depth level

Visualization

Tap to expand

Step-by-Step Walkthrough

Track Depth

Use counter to track current nesting depth

Alternate Assignment

Assign parentheses based on depth parity (even→0, odd→1)

Minimize Maximum

This distribution ensures minimum possible maximum depth

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(const char* seq) {
    int n = strlen(seq);
    int* result = (int*)malloc(n * sizeof(int));
    int depth = 0;
    
    for (int i = 0; i < n; i++) {
        if (seq[i] == '(') {
            // Assign based on current depth parity
            result[i] = depth % 2;
            depth++;
        } else { // seq[i] == ')'
            // Decrement depth first
            depth--;
            // Then assign based on the depth of the matching '('
            result[i] = depth % 2;
        }
    }
    
    return result;
}

int main() {
    char seq[10000];
    fgets(seq, sizeof(seq), stdin);
    seq[strcspn(seq, "\n")] = 0;
    
    int* result = solution(seq);
    int n = strlen(seq);
    printf("[");
    for (int i = 0; i < n; i++) {
        printf("%d", result[i]);
        if (i < n - 1) printf(",");
    }
    printf("]\n");
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string with constant operations per character

✓ Linear Growth

Space Complexity

O(1)

Only uses a few variables to track depth and assignment

✓ Linear Space

42.0K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Stack-Based Depth Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler