Intuition | 0(N) | O(1) | Detailed Explanation | C++ | ✅
Intuition\n Describe your first thoughts on how to solve this problem. \nWe are given a string s of even length consisting of equal numbers of opening brackets 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe are given a string s of even length consisting of equal numbers of opening brackets [ and closing brackets ]. The task is to determine the minimum number of swaps required to make the string balanced.\n\nA balanced string is defined as either:\n\n- An empty string.\n- A string that can be written as **AB**, where both **A** and **B** are balanced strings.\n- A string that can be written as **[C]**, where **C** is a balanced string.\n\n\n**Key Insight:**\nThe primary idea is that we shouldn\'t disturb any portion of the string that is already balanced, as this would only increase the number of swaps needed. Thus, we need to focus on only the **unbalanced** parts of the string.\n\n\n**Analyzing the Unbalanced Part:**\nLet\u2019s first understand what an unbalanced section looks like. Consider a string like **][][** :\nThe first **]** is a closing bracket that cannot be matched with any opening bracket before it.\nSimilarly, the **[** at the end is an opening bracket that cannot be matched with any closing bracket after it.\nThus, these form the unbalanced part.\nTo visualize, imagine removing all the valid balanced sections of the string. The remaining part would always have the form **]]]]]...[[[[[** \n\n**Why?**\n\nAny unmatched closing bracket ] comes before unmatched opening brackets [, forming an alternating pattern of closing followed by opening brackets.\nIf a closing bracket came after a opening bracket that dosent have a equivalent closing bracket ahead will balance the opening bracket.\nFor example, in the string **]]][][[]][[[** the closing brackets at index 4 , 7 and 8 are balancing the opening brackets so they are part of a valid paranthesis. so here the portion from index **0 to 2** is **invalid** and **3 to 8** is **valid** and from **9 to 11** is **invalid**.\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**Minimizing Swaps:**\nNow that we have identified the unbalanced part, we need to minimize the number of swaps required to balance it. The minimum way to make **]]][[[** valid is to swap a closing bracket **]** with an opening bracket **[**. The key observation here is that:\n\nIf we swap a closing bracket **]** with an opening bracket **[**, we will surely eliminate one pair of unmatched brackets.\nBut instead if we swap the unmatched closing bracket **]** with the unmatched opening bracket **[** that has a opening bracket ahead then we could elimiate two pairs of unmatches brackets. This maximizes the number of brackets eliminated in a single swap.\n\nFor example, in the string **]]][[[**, swapping the first closing bracket ] with the last or second last opening bracket **[** gives **[]]][[]**, we could elimiate 4 brackets . Lets say we swap 0th and 4th index then we will have **[]][][** so now the only invalid part remaining is index 2 and index 5 **][** .\n\n\nSolution: \nWe just need to find the number of unbalanced closing brackets, which are the **]** brackets which dont have a opening bracket **[** to pair with.   \u200B\n \n\nThus, the total number of swaps required to balance the string is the number of unbalanced closing brackets (or opening brackets) divided by 2, since every swap fixes two unbalanced brackets if even and +1 if odd as the there will be one swap which will only eliminate one unbalanced closing bracket.\n\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(1)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int minSwaps(string s) {\n        int open = 0;  // Count of unmatched opening brackets\n        int unbalancedClose = 0;  // Count of unbalanced closing brackets\n        \n        // Iterate through each character in the string\n        for(char c : s) {\n            if(c == \'[\') {\n                open++;  // Increment count for unmatched opening bracket\n            } else {  // c == \']\'\n                if(open > 0) {\n                    open--;  // A matched pair is found, so decrement open\n                } else {\n                    unbalancedClose++;  // No opening bracket to match with, so increment unbalanced closing bracket count\n                }\n            }\n        }\n        \n        // The minimum swaps needed are the half of unbalanced closing brackets if even and +1 if odd.\n        \n        return (unbalancedClose / 2) + (unbalancedClose % 2) ;\n    }\n};\n\n```
['String', 'Greedy', 'C++']