EASY TWO POINTER APPROACH 😊|| EASY TO UNDERSTAND✅ || TWO POINTER
Intuition\n Describe your first thoughts on how to solve this problem. \nTo achieve a valid bracket sequence, we need to ensure that for every closing bracket ]
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo achieve a valid bracket sequence, we need to ensure that for every closing bracket ], there exists a preceding opening bracket [. The key intuition here is to keep track of the balance between these two types of brackets as we iterate through the string. Whenever we find an imbalance (more ] than [ at any point), we know that we need to perform a swap to bring the brackets into a valid order.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Balance Tracking (diff):\n\n- When we encounter [, we increase diff because it contributes to an opening bracket.\n- When we encounter ], we decrease diff because it closes an opening bracket.\n- If diff becomes negative, it means there are more closing brackets (]) than opening brackets ([), indicating an imbalance.\n\n2. Swapping Logic:\n\n- When the imbalance occurs (diff < 0), we need to swap an opening bracket [ from the right side of the string with the closing bracket ] on the left to restore balance.\n- We then move both pointers inward and continue processing the rest of the string.\n\n3. Two-Pointer Technique:\n\n- left starts at the beginning of the string and moves rightwards.\n- right starts at the end of the string and moves leftwards.\n- When an imbalance is detected, we move right to find a [ for swapping.\n\n4. Resetting the Balance After Swapping:\n- After swapping, we reset diff to 1 because the swap balances one ], but it also introduces an extra [ which is now unbalanced, so we continue tracking it.\n\n# Complexity\n- Time complexity: The time complexity is O(n), where n is the length of the string, because we make a single pass through the string using the left pointer, and the right pointer only moves when necessary, making the overall complexity linear\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: The space complexity is O(1) since we are using a constant amount of extra space.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int minSwaps(string s) {\n        int diff = 0;\n        int left = 0, right = s.size()-1;\n        int swaps = 0;\n        while(left < right){\n            if(s[left] == \'[\'){\n                diff++;\n            }\n            else if(s[left] == \']\'){\n                diff--;\n            }\n            if(diff < 0){\n                while(s[right] != \'[\' && left < right){\n                    right--;\n                }\n                swap(s[left], s[right]);\n                right--;\n                diff =1;\n\n                swaps++;\n            }\n            left++;\n        }\n        return swaps;\n    }\n};\n```
['Two Pointers', 'String', 'C++']