# 1963. Minimum Number of Swaps to Make the String Balanced
###### tags: `Leetcode` `Medium` `Parentheses` `Greedy`
Link: https://leetcode.com/problems/minimum-number-of-swaps-to-make-the-string-balanced/description/
## 思路
本题的关键点是要想到，如果把所有能就近配对的括号都消去的话，剩余的括号必然是形如```]]]][[[[[```的模式。这些位于两边的括号是无论如何都无法在原字符串里被匹配的。

对于连续n个右括号+连续n个左括号，需要多少次swap能够让他们配对呢？我们不妨多尝试几个例子：

][: => [] 1 swap
]][[: => [][] 1 swap
]]][[[: => []][[] => [][][] 2 swaps
]]]][[[[: => []]][[[] => [][][][] 2 swaps

所以我们可以总结出规律来，只需要(n+1)/2次交换。
## Code

class Solution {
    public int minSwaps(String s) {
        int n = s.length();
        int left = 0;
        for(int i=0; i<n; i++){
            if(s.charAt(i)=='[') left++;
            else{
                if(left==0) continue;
                else left--;
            }
        }
        return (left+1)/2;
    }
}