Maximum Nesting Depth of Two Valid Parentheses Strings - Solution & Explanation

Problem Overview: You receive a valid parentheses string s. The task is to split it into two valid parentheses strings A and B such that the maximum nesting depth across both strings is minimized. Instead of constructing the strings directly, you return an array where each index indicates whether that parenthesis belongs to sequence 0 or 1.

The key observation: nesting depth increases when you see ( and decreases when you see ). If you distribute parentheses between two groups while tracking depth, you can ensure neither group accumulates excessive nesting.

Approach 1: Alternating Depth Approach (O(n) time, O(1) space)

This method tracks the current nesting depth while iterating through the string once. Each time you encounter (, increment the depth and assign the parenthesis to group depth % 2. When you see ), assign it using the current depth parity before decrementing. This effectively alternates nested layers between the two groups.

The insight: alternating by depth splits the nesting tree into two balanced halves. Deep levels automatically go to different groups, preventing one sequence from accumulating all the nesting. The algorithm performs a single pass through the string and only maintains an integer depth counter.

This approach is extremely concise and avoids auxiliary structures like stacks. If you already understand how nesting depth evolves in a valid parentheses string, this solution becomes almost mechanical.

Approach 2: Balanced Depth Assignment (O(n) time, O(1) space)

This approach also scans the string once but focuses on balancing how opening and closing parentheses are distributed between the two groups. Maintain a depth counter and decide the assignment based on whether the current level is even or odd. Opening parentheses increase the depth, and closing parentheses decrease it, while assignments ensure both sequences stay balanced.

The idea is similar to splitting a recursion tree into two interleaving layers. Each depth level alternates ownership between the two sequences, guaranteeing that the deepest nesting in the original string gets divided. This keeps the maximum depth of each resulting string close to originalDepth / 2.

Because the input is guaranteed to be valid, no explicit stack is required. A simple counter replaces the usual stack-based parsing commonly used for string parentheses problems.

Recommended for interviews: The alternating depth approach is the expected solution. It runs in O(n) time with O(1) extra space and demonstrates that you understand how nesting depth evolves in a parentheses string. Showing awareness of the depth distribution idea proves you can optimize beyond naive stack simulations.