Clear Explanation || C++ || Greedy || Detailed Explanation
Idea : \n\nFor such kind of problems first thing that should hit our mind is can we solve it Greedily. It is a variation of Balanced Parenthesis problem.\n\nThe
**Idea :** \n\nFor such kind of problems first thing that should hit our mind is can we solve it **Greedily**. It is a variation of Balanced Parenthesis problem.\n\nThese kind of problems are hard to proof, one need to rely on their own intution during contest I think xD. \n\nNow lets observe somthings that are given in the question. \n* First of all it is guarenteed that total number of \'[\' brackets is equal to total number of \']\' brackets. \n* So, for every bracket element we are sure that its counterpart exist.\n* Also, to keep string balanced, at every i \n\t* *count of \'[\' >= count of \']\'*\n\t* If at any moment *count of \']\'* exceeds *count of \'[\'*, this is the time when we need to do swaping.\n\nAs of now that we have noted few important observations, lets move to algorithm part. \n1. To track if brackets are balanced at any index i, lets take a variable *balance* \n\t* balance = 0 , initially\n\t\t\n2. When we see a opening bracket, we increament balance by one. \n\t * As we expect a closing bracket later who will balance it . \'[\' -> 1\n\t\t \n3. Else When we see closing bracket, we decrement balance by one so that number \n\t* this will balance the opening bracket that occured previously. \']\' -> -1\n\t\t\t\n\t\t\tstring:    [   [    ]   ] \n\t\t\tbalance:   1   2    1   0   \n\t\t\t\t\t(at last balance is zero which means all elements are matched)\n\t\t\t\n4. Now, the main catch where we need to swap. When number of closing brackets exceed the already occured opening brackets. This is where we need to do swapping.\n\t* when *balance < 0*, or *balance == -1* , swap this element with first occuring \'[\' from last. \n\t* Doing this we change our current balance to 1 and now we can move further in search of closing brackets.\n\t\t\n\t\t\tstring:     [      ]       ]          [\n\t\t\tbalance :\t (1)    (0)    (-1)  ....  (1)  \n\t\t\t// Swap (-1) with the last (1) to balance it\n\t\t\n\t* As soon as we swap the brackets, we need to again set balance to 1 as current bracket is opening -> \'[\' = 1\n\nLets Do a dry run on string : "[ ] ] ] [ [ ] ["\n\t\n\tindex:   0  1  2  3  4  5  6  7\n\tstring : [  ]  ]  ]  [  [  ]  [\n\tbalance: 1  0 -1  .  .  .  .  .\n\t-> swap \']\' at index 2 with first \'[\' from last i.e index 7\n\t=> swap = 1 , set balance to 1 \n\t\n\tAfter swapping we continue till end until balance does not become -1. \n\tIf balance = -1, repeat above steps\n\t\n\tindex:   0  1  2  3  4  5  6  7\n\tstring : [  ]  [  ]  [  [  ]  ]\n\tbalance: 1  0  1  0  1  2  1  0  \n\t-> This is final value of balance and state string that is balanced\n\t\t\n\n**Code**\n\n```\nint minSwaps(string s) {\n\tint n = s.size();\n\tint balance = 0, swaps = 0, j=n-1;\n\tfor(int i=0; i<n; i++)\n\t{\n\t\tif(s[i] == \'[\') balance++;\n\t\telse balance--;\n\n\t\tif(balance < 0)\n\t\t{\n\t\t\twhile(i<j && s[j] != \'[\') j--;\n\t\t\tswap(s[i], s[j]);\n\t\t\tswaps++;\n\t\t\tbalance = 1;\n\t\t}\n\t}\n\treturn swaps;\n}\n```\n**Time : O(N)**\n**Space : O(1)**\n\n**Hope this explanation was crystal clear. In case of any query let me know :)**\n**If you liked my explanation do upvote !!!**\n\n\nAlso practice Similar Problems : \n1. [Minimum Add to Make Parenthesis Valid](https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/)\n2. [Minimum Remove to Remove Make Valid Parenthesis](https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/)\n3. [Minimum Insertions to balance a parenthesis string](https://leetcode.com/problems/minimum-insertions-to-balance-a-parentheses-string/)\n4. [Remove Invalid Parenthesis](https://leetcode.com/problems/remove-invalid-parentheses/)\n
['Two Pointers', 'Greedy', 'C']