使字符串平衡的最小交换次数

You are given a 0-indexed string s of even length n. The string consists of exactly n / 2 opening brackets '[' and n / 2 closing brackets ']'.

A string is called balanced if and only if:

• It is the empty string, or
• It can be written as AB, where both A and B are balanced strings, or
• It can be written as [C], where C is a balanced string.

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

Return the minimum number of swaps to make s balanced.

 

Example 1:

Input: s = "][]["
Output: 1
Explanation: You can make the string balanced by swapping index 0 with index 3.
The resulting string is "[[]]".

Example 2:

Input: s = "]]][[["
Output: 2
Explanation: You can do the following to make the string balanced:
- Swap index 0 with index 4. s = "[]][][".
- Swap index 1 with index 5. s = "[[][]]".
The resulting string is "[[][]]".

Example 3:

Input: s = "[]"
Output: 0
Explanation: The string is already balanced.

 

Constraints:

• n == s.length
• 2 <= n <= 106
• n is even.
• s[i] is either '[' or ']'.
• The number of opening brackets '[' equals n / 2, and the number of closing brackets ']' equals n / 2.

此题解采用贪心算法的思路来解决问题。首先初始化一个计数器 cnt 来记录遇到的未匹配的 ']' 的数量。遍历字符串，每次遇到 ']' 且 cnt 大于 0 时，说明前面有一个 '[' 可以与之匹配，因此将 cnt 减一。如果遇到 '[' 或者 cnt 为 0 时遇到 ']'，则 cnt 加一。最后，cnt 表示的是无法匹配的 '[' 的数量（每个这样的 '[' 都需要一个对应的 ']' 来匹配以平衡字符串）。因此，需要的最小交换次数为 cnt 的一半，因为每一次交换可以解决两个未匹配的括号。

O(n)

O(1)