Intuition better than editorial | Detailed Explanation | Stack
Intuition\nA string of parentheses is considered balanced when every opening bracket [ has a corresponding closing bracket ] in the correct order (i.e., [ comes
# Intuition\nA string of parentheses is considered balanced when every opening bracket `[` has a corresponding closing bracket `]` in the correct order (i.e., `[` comes before `]`). An unbalanced string occurs when a `]` appears before its corresponding `[`. The goal is to minimize the number of swaps required to balance the string.\n\nThe key insight is that we should avoid touching already balanced pairs of parentheses since doing so may introduce new imbalances. Instead, we focus solely on the unbalanced parts of the string. Unbalanced pairs arise when we encounter a `]` without a preceding `[`. These unbalanced pairs are the central issue we need to resolve.\n\nFurther intuition reveals that two unbalanced parentheses can be corrected with one swap. For example, consider the string `"]][["`, which contains two unbalanced pairs. By swapping the first and last characters, the string becomes `"[][]"`, which is balanced. Therefore, the problem reduces to counting the number of unbalanced pairs. Since each swap fixes two unbalanced parentheses, the number of swaps required is half the number of unbalanced pairs. If the total number of unbalanced parentheses is odd, we would need an additional swap to handle the last pair, so we take the ceil value of `unbalancedPairs / 2`.\n\n# Approach\nWe can track the unbalanced pairs using a stack. By including only unbalanced pairs in the stack and excluding already balanced pairs, we can determine how many swaps are needed.\n\n- Use a stack to track unbalanced parentheses:\n    - For each `[`, push it onto the stack.\n    - For each `]`, if the stack has a `[` on top, pop it (indicating a balanced pair). Otherwise, push the ] (indicating an unbalanced pair).\n- After processing the string, the stack will contain only unbalanced pairs.\n- Stack contains both opening and closing brackets, so the count of unbalances pairs is `stack.size() / 2`.\n- Number of swaps required would be `unbalancedPairs / 2`.\n\n# Complexity\n- Time complexity: $$O(n)$$, where n is the length of the string. We perform a single pass through the string and use constant-time stack operations.\n\n- Space complexity: $$O(n)$$, for storing unbalanced parentheses in the stack.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int minSwaps(string s) {\n        stack<char> st; // Stack to track unbalanced parentheses\n\n        for(auto &i : s)\n            if(i == \'[\')\n                st.push(i); // Push opening bracket to the stack\n            else if(!st.empty() && st.top() == \'[\')\n                st.pop(); // Excluding balanced pairs\n            else\n                st.push(i); // Push closing bracket to the stack\n\n        int unbalancedPairs = st.size() / 2;\n        int swaps = ceil(unbalancedPairs / 2.0);\n        return swaps;\n    }\n};\n```\n```java []\nclass Solution {\n    public int minSwaps(String s) {\n        Stack<Character> st = new Stack<>(); // Stack to track unbalanced parentheses\n        \n        for (char i : s.toCharArray())\n            if (i == \'[\')\n                st.push(i); // Push opening bracket to the stack\n            else if (!st.isEmpty() && st.peek() == \'[\')\n                st.pop(); // Excluding balanced pairs\n            else\n                st.push(i); // Push closing bracket to the stack\n        \n        int unbalancedPairs = st.size() / 2;\n        int swaps = (int) Math.ceil(unbalancedPairs / 2.0);\n        return swaps;\n    }\n}\n```\n```python3 []\nclass Solution:\n    def minSwaps(self, s: str) -> int:\n        st = [] # Stack to track unbalanced parentheses\n        \n        for i in s:\n            if i == \'[\':\n                st.append(i) # Push opening bracket to the stack\n            elif st and st[-1] == \'[\':\n                st.pop() # Excluding balanced pairs\n            else:\n                st.append(i) # Push closing bracket to the stack\n        \n        unbalancedPairs = len(st) // 2\n        swaps = math.ceil(unbalancedPairs / 2.0)\n        return swaps\n```\n```javascript []\nvar minSwaps = function(s) {\n    let st = []; // Stack to track unbalanced parentheses\n    \n    for (let i of s)\n        if (i === \'[\')\n            st.push(i); // Push opening bracket to the stack\n        else if (st.length > 0 && st[st.length - 1] === \'[\')\n            st.pop(); // Excluding balanced pairs\n        else\n            st.push(i); // Push closing bracket to the stack\n    \n    let unbalancedPairs = st.length / 2;\n    let swaps = Math.ceil(unbalancedPairs / 2.0);\n    return swaps;\n};\n```\n\n***Note** : This problem can also be solved without using a stack. An alternative space-optimized approach is discussed in Approach 2 of the editorial.*\n\n![Upvote.png](https://assets.leetcode.com/users/images/13bdbdce-25ec-426c-bd3a-3b74db77b59b_1728366274.9831467.png)\n
['Stack', 'C++', 'Java', 'Python3', 'JavaScript']