DDSA Solutions

1111. Maximum Nesting Depth of Two Valid Parentheses Strings

MediumView on LeetCode
StringStack

Problem Overview

The goal is to split one valid parentheses string into two valid strings so the deeper of the two is as shallow as possible.

Intuition

The goal is to split one valid parentheses string into two valid strings so the deeper of the two is as shallow as possible. If the original depth is d, one group has to hold at least half of it. Sending alternate nesting levels to alternate groups reaches that bound: odd levels go to one group and even levels to the other. The depth before any index has the same parity as the index itself, so the group can be read straight from the index without tracking depth.

Algorithm

  1. 1Create an answer array the same length as the string.
  2. 2For each index i, start with i % 2.
  3. 3If the character is a closing parenthesis, flip that bit.
  4. 4Store the result as the group for that character and return the array.

Example Walkthrough

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

  1. 1.The outer pair sits at indexes 0 and 5 and both get group 0.
  2. 2.The two inner pairs sit at indexes 1 through 4 and all get group 1.
  3. 3.Group 0 is "()" and group 1 is "()()", so each has depth 1 while the original depth is 2.

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

Common Pitfalls

  • •Any optimal split is accepted, so the labels may differ from the sample as long as both depths stay minimal.
  • •An opening parenthesis and its matching close must land in the same group, or that group stops being valid.
  • •Before index i, the opens minus closes has the same parity as i. That is why flipping for a closing parenthesis keeps each pair together.
  • •Putting each whole top level pair in one group does not help, because a single deep pair keeps its full depth.
1111.cs
C#
// Approach: Alternate nesting levels between the two groups, so each group
// gets about half of the maximum depth. The depth before index i has the
// same parity as i, so an opening parenthesis goes to group i % 2 and its
// matching close lands on the opposite parity index with the same group.
// Complexity: O(n) time, O(1) extra space beyond the output.
public class Solution
{
    public int[] MaxDepthAfterSplit(string seq)
    {
        int[] ans = new int[seq.Length];
        for (int i = 0; i < seq.Length; i++)
            ans[i] = (i & 1) ^ (seq[i] == ')' ? 1 : 0);
        return ans;
    }
}
Was this solution helpful?

Related Problems