Split Parentheses to Minimize the Larger Depth
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
The input seq is a valid parentheses string. Assign every character to subsequence A or B while preserving order in each, so both are valid parentheses strings. Empty subsequences are valid. Return a 0/1 assignment minimizing the larger nesting depth of A and B; 0 selects A and 1 selects B. Any optimal assignment is acceptable. Nesting depth is the maximum number of unmatched opening parentheses in a prefix, or 0 for an empty string.
```cpp
class Solution {
public:
vector<int> maxDepthAfterSplit(string seq);
};
```
### Examples
**Example 1:**
```text
Input: seq = "((()))"
Output: [0,1,0,0,1,0]
Explanation: A is(()), of depth2; B is(), of depth1. Original depth3 forces at least one subsequence to have depth2.
```
**Example 2:**
```text
Input: seq = "()()"
Output: [0,0,0,0]
Explanation: A has depth1 and B is empty. A nonempty original string cannot have optimum depth0.
```
### Constraints
- The valid parentheses string has length between 1 and 10000.
- Its characters are only `(` and `)`; validity is part of the original premise.
### Contract considerations
The original input is guaranteed valid; no lexicographic tie-break is required for the bit array.
```hint Read the boundary condition
May either assigned subsequence be empty, and must every original character be assigned exactly once?
```
### What a Strong Answer Covers
The original input is guaranteed valid; no lexicographic tie-break is required for the bit array.
### Follow-up Questions
Optional practice extension, separate from the original task: How would the depth objective change when splitting into more than two valid subsequences?
Overview: Split Parentheses to Minimize the Larger Depth. The input seq is a valid parentheses string. Assign every character to subsequence A or B while preserving order in each, so both are valid parentheses strings.
