Package g1901_2000.s1963_minimum_number_of_swaps_to_make_the_string_balanced

Class Solution

java.lang.Object
g1901_2000.s1963_minimum_number_of_swaps_to_make_the_string_balanced.Solution
public class Solution extends Object
1963 - Minimum Number of Swaps to Make the String Balanced.<p>Medium</p> <p>You are given a <strong>0-indexed</strong> string <code>s</code> of <strong>even</strong> length <code>n</code>. The string consists of <strong>exactly</strong> <code>n / 2</code> opening brackets <code>'['</code> and <code>n / 2</code> closing brackets <code>']'</code>.</p> <p>A string is called <strong>balanced</strong> if and only if:</p> <ul> <li>It is the empty string, or</li> <li>It can be written as <code>AB</code>, where both <code>A</code> and <code>B</code> are <strong>balanced</strong> strings, or</li> <li>It can be written as <code>[C]</code>, where <code>C</code> is a <strong>balanced</strong> string.</li> </ul> <p>You may swap the brackets at <strong>any</strong> two indices <strong>any</strong> number of times.</p> <p>Return <em>the <strong>minimum</strong> number of swaps to make</em> <code>s</code> <em><strong>balanced</strong></em>.</p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> s = &ldquo;][][&rdquo;</p> <p><strong>Output:</strong> 1</p> <p><strong>Explanation:</strong> You can make the string balanced by swapping index 0 with index 3. The resulting string is &ldquo;[ []]&rdquo;.</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> s = &ldquo;]]][[[&rdquo;</p> <p><strong>Output:</strong> 2</p> <p><strong>Explanation:</strong> You can do the following to make the string balanced:</p> <ul> <li> <p>Swap index 0 with index 4. s = &ldquo;[]][][&rdquo;.</p> </li> <li> <p>Swap index 1 with index 5. s = &ldquo;[ [][]]&rdquo;. The resulting string is &ldquo;[ [][]]&rdquo;.</p> </li> </ul> <p><strong>Example 3:</strong></p> <p><strong>Input:</strong> s = &ldquo;[]&rdquo;</p> <p><strong>Output:</strong> 0</p> <p><strong>Explanation:</strong> The string is already balanced.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>n == s.length</code></li> <li><code>2 <= n <= 10<sup>6</sup></code></li> <li><code>n</code> is even.</li> <li><code>s[i]</code> is either <code>'['</code> or <code>']'</code>.</li> <li>The number of opening brackets <code>'['</code> equals <code>n / 2</code>, and the number of closing brackets <code>']'</code> equals <code>n / 2</code>.</li> </ul>

  • Constructor Details

    • Solution

      public Solution()

  • Method Details

    • minSwaps

      public int minSwaps(String s)