LeetCode 1963. Minimum Number of Swaps to Make the String Balanced

原题链接在这里：https://leetcode.com/problems/minimum-number-of-swaps-to-make-the-string-balanced/

题目：

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.

题解：

Disregard all the solid pairs. 

Find out the number of unsolid pairs count.

The minimum swap number is the ceiling of count/2.

Time Complexity: O(n). n = s.length().

Space: O(1).

AC Java:

 1 class Solution {  2     public int minSwaps(String s) {  3         if(s == null || s.length() == 0){  4             return 0;  5         }  6           7         int count = 0;  8         for(int i = 0; i < s.length(); i++){  9             char c = s.charAt(i); 10             if(c == '['){ 11                 count++; 12             }else if(count > 0){ 13                 count--; 14             } 15         } 16          17         return (count + 1) / 2; 18     } 19 }

类似Minimum Add to Make Parentheses Valid, Minimum Remove to Make Valid Parentheses.