minimum-number-of-swaps-to-make-the-string-balanced

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a 0-indexed string <code>s</code> of even length <code>n</code>. The string consists of exactly <code>n / 2</code> opening brackets <code>&#39;[&#39;</code> and <code>n / 2</code> closing brackets <code>&#39;]&#39;</code>.

A string is called balanced if and only if:

<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 balanced strings, or</li>
	<li>It can be written as <code>[C]</code>, where <code>C</code> is a balanced string.</li>
</ul>

You may swap the brackets at any two indices any number of times.

Return the minimum number of swaps to make <code>s</code> balanced.

&nbsp;
Example 1:

<pre>
Input: s = &quot;][][&quot;
Output: 1
Explanation: You can make the string balanced by swapping index 0 with index 3.
The resulting string is &quot;[[]]&quot;.
</pre>

Example 2:

<pre>
Input: s = &quot;]]][[[&quot;
Output: 2
Explanation: You can do the following to make the string balanced:
- Swap index 0 with index 4. s = &quot;[]][][&quot;.
- Swap index 1 with index 5. s = &quot;[[][]]&quot;.
The resulting string is &quot;[[][]]&quot;.
</pre>

Example 3:

<pre>
Input: s = &quot;[]&quot;
Output: 0
Explanation: The string is already balanced.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>n == s.length</code></li>
	<li><code>2 &lt;= n &lt;= 106</code></li>
	<li><code>n</code> is even.</li>
	<li><code>s[i]</code> is either <code>&#39;[&#39; </code>or <code>&#39;]&#39;</code>.</li>
	<li>The number of opening brackets <code>&#39;[&#39;</code> equals <code>n / 2</code>, and the number of closing brackets <code>&#39;]&#39;</code> equals <code>n / 2</code>.</li>
</ul>

minSwaps

Minimum Number of Swaps to Make the String Balanced

Remove Invalid Parentheses

remove-invalid-parentheses

删除无效的括号

Minimum Add to Make Parentheses Valid

minimum-add-to-make-parentheses-valid

使括号有效的最少添加

Minimum Remove to Make Valid Parentheses

minimum-remove-to-make-valid-parentheses

移除无效的括号

Minimum Insertions to Balance a Parentheses String

minimum-insertions-to-balance-a-parentheses-string

平衡括号字符串的最少插入次数

Stack

Greedy

Two Pointers

String

给你一个字符串 <code>s</code> ，下标从 0 开始 ，且长度为偶数 <code>n</code> 。字符串 恰好 由 <code>n / 2</code> 个开括号 <code>'['</code> 和 <code>n / 2</code> 个闭括号 <code>']'</code> 组成。

只有能满足下述所有条件的字符串才能称为 平衡字符串 ：

<ul>
	<li>字符串是一个空字符串，或者</li>
	<li>字符串可以记作 <code>AB</code> ，其中 <code>A</code> 和 <code>B</code> 都是 平衡字符串 ，或者</li>
	<li>字符串可以写成 <code>[C]</code> ，其中 <code>C</code> 是一个 平衡字符串 。</li>
</ul>

你可以交换 任意 两个下标所对应的括号 任意 次数。

返回使 <code>s</code> 变成 平衡字符串 所需要的 最小 交换次数。

&nbsp;

示例 1：

<pre>
输入：s = "][]["
输出：1
解释：交换下标 0 和下标 3 对应的括号，可以使字符串变成平衡字符串。
最终字符串变成 "[[]]" 。
</pre>

示例 2：

<pre>
输入：s = "]]][[["
输出：2
解释：执行下述操作可以使字符串变成平衡字符串：
- 交换下标 0 和下标 4 对应的括号，s = "[]][][" 。
- 交换下标 1 和下标 5 对应的括号，s = "[[][]]" 。
最终字符串变成 "[[][]]" 。
</pre>

示例 3：

<pre>
输入：s = "[]"
输出：0
解释：这个字符串已经是平衡字符串。
</pre>

&nbsp;

提示：

<ul>
	<li><code>n == s.length</code></li>
	<li><code>2 &lt;= n &lt;= 106</code></li>
	<li><code>n</code> 为偶数</li>
	<li><code>s[i]</code> 为<code>'['</code> 或 <code>']'</code></li>
	<li>开括号 <code>'['</code> 的数目为 <code>n / 2</code> ，闭括号 <code>']'</code> 的数目也是 <code>n / 2</code></li>
</ul>