Package g1101_1200.s1111_maximum_nesting_depth_of_two_valid_parentheses_strings

Class Solution

java.lang.Object

g1101_1200.s1111_maximum_nesting_depth_of_two_valid_parentheses_strings.Solution

public class Solution
extends Object

1111 - Maximum Nesting Depth of Two Valid Parentheses Strings.<p>Medium</p> <p>A string is a <em>valid parentheses string</em> (denoted VPS) if and only if it consists of <code>&quot;(&quot;</code> and <code>&quot;)&quot;</code> characters only, and:</p> <ul> <li>It is the empty string, or</li> <li>It can be written as <code>AB</code> (<code>A</code> concatenated with <code>B</code>), where <code>A</code> and <code>B</code> are VPS&rsquo;s, or</li> <li>It can be written as <code>(A)</code>, where <code>A</code> is a VPS.</li> </ul> <p>We can similarly define the <em>nesting depth</em> <code>depth(S)</code> of any VPS <code>S</code> as follows:</p> <ul> <li><code>depth(&quot;&quot;) = 0</code></li> <li><code>depth(A + B) = max(depth(A), depth(B))</code>, where <code>A</code> and <code>B</code> are VPS&rsquo;s</li> <li><code>depth(&quot;(&quot; + A + &quot;)&quot;) = 1 + depth(A)</code>, where <code>A</code> is a VPS.</li> </ul> <p>For example, <code>&quot;&quot;</code>, <code>&quot;()()&quot;</code>, and <code>&quot;()(()())&quot;</code> are VPS&rsquo;s (with nesting depths 0, 1, and 2), and <code>&quot;)(&quot;</code> and <code>&quot;(()&quot;</code> are not VPS&rsquo;s.</p> <p>Given a VPS seq, split it into two disjoint subsequences <code>A</code> and <code>B</code>, such that <code>A</code> and <code>B</code> are VPS&rsquo;s (and <code>A.length + B.length = seq.length</code>).</p> <p>Now choose <strong>any</strong> such <code>A</code> and <code>B</code> such that <code>max(depth(A), depth(B))</code> is the minimum possible value.</p> <p>Return an <code>answer</code> array (of length <code>seq.length</code>) that encodes such a choice of <code>A</code> and <code>B</code>: <code>answer[i] = 0</code> if <code>seq[i]</code> is part of <code>A</code>, else <code>answer[i] = 1</code>. Note that even though multiple answers may exist, you may return any of them.</p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> seq = &ldquo;(()())&rdquo;</p> <p><strong>Output:</strong> [0,1,1,1,1,0]</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> seq = &ldquo;()(())()&rdquo;</p> <p><strong>Output:</strong> [0,0,0,1,1,0,1,1]</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= seq.size <= 10000</code></li> </ul>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
int[]	maxDepthAfterSplit(String seq)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

maxDepthAfterSplit

public int[] maxDepthAfterSplit(String seq)