How to reach the optimal solution | Explained with Intuition and Diagram
------Please upvote! if you like the solution and explanation.  Please put your doubts/queries in the comments section below.  I will try my best to answer them
*------Please **upvote!** if you like the solution and explanation.  Please put your doubts/queries in the comments section below.  I will try my best to answer them.------*\n\n**Intuition:**\n\nWe can discard the balanced components from our input string as they will not matter in balancing the string.  Now, after excluding them, we will find that all the unbalanced brackets look like this:\n\n**]]]]]\u2026..[[[[[\u2026..**\n\nNow, since we can swap any pair of brackets, the **optimal approach is to balance 2 sets of brackets at a time using 1 swap** (hinting at `result = total unbalanced / 2`, which we will handle for **even and odd lengths** together).  Take this for example:\n\n![image](https://assets.leetcode.com/users/images/bf90f2ec-963a-43cd-829d-8ed3fa2a9268_1628395747.9635198.png)\n\nSo, following this, we will notice a pattern (try out the same with different number of mismatches to see the pattern):\n\n![image](https://assets.leetcode.com/users/images/0731629f-ae07-4507-bfc4-a7b1bea289b6_1628395785.653253.png)\n\nSo, our result (min. swaps) = **`(mismatches + 1) / 2`**\n\n***The key here is to start balancing from the middle.***\n\n\n```\nclass Solution {\n    public int minSwaps (String s) {\n        Stack <Character> stack = new Stack ();\n        int mismatch = 0;\n        for (int i = 0; i < s.length (); i++) {\n            char ch = s.charAt (i);\n            if (ch == \'[\')\n                stack.push (ch);\n            else {\n                if (!stack.isEmpty ())\n                    stack.pop ();\n                else \n                    mismatch++;\n            }\n        }\n        return (mismatch + 1) / 2;\n    }\n}\n```\n\n**Update:** As suggested by quite a few people in the comments, here is the Space Optimized Approach which removes the need of the stack.  We will simply use a variable **`stack_size`** to keep track of mismatches.  If the current character is a **\'[\'**, then we increment **`stack_size`**, else, we decrement it only if it is **greater than 0** (meaning we have seen some valid [ brackets before, so this ] bracket is going to balance them out).  At the end, **`stack_size`** will contain the count of brackets which are not balanced, i.e **`[[[[[....`**.  *Code below:*\n\n```\nclass Solution {\n    public int minSwaps (String s) {\n        int stack_size = 0;\n        for (int i = 0; i < s.length (); i++) {\n            char ch = s.charAt (i);\n            if (ch == \'[\')\n                stack_size++;\n            else {\n                if (stack_size > 0)\n                    stack_size--;\n            }\n        }\n        return (stack_size + 1) / 2;\n    }\n}\n```\n\nPlease **upvote!** if you like the solutions.\n
['Java']