Stack Explained with Examples || Python
Intuition\nIterate over given \'s\' and if balanced parenthesis then remove them. How?\nMaintain a stack and if \'[\' found and put in the index. If \']\' found
# Intuition\n`Iterate over given \'s\' and if balanced parenthesis then remove them. How?`\nMaintain a stack and if \'[\' found and put in the index. If \']\' found and there is already some value in stack pop the top and make both index as "". (As they are balanced now) \nIf the stack is empty move forward as no paranthesis found to balance it.\nAfter removing all the balanced paranthesis check if s is empty then no swap is required.\nElse perform a swap over the obtained new list.\n`why left + 2 and right -2 instead of left +1 and right -1?`\nobserve an eg -> ] ] [ [\nafter first swap -> [ ] [ ]\nso left + 1 is already baalnced with new left and right - 1 is already balanced with new right.\neg 2 -> ] ] ] [ [ [\nafter first swap -> [ ] ] ] [ [ ]\nagain, left + 1 is already baalnced with new left and right - 1 is already balanced with new right so move pointer to left + 2 and right -2.\nreturn no of swaps u required gives u the ans\n\n# Code\n```\nclass Solution:\n    def minSwaps(self, s: str) -> int:\n        stack = []\n        s = list(s)\n        for i in range(len(s)):\n            if s[i] == \'[\':\n                stack.append(i)\n            if s[i] == \']\' and len(stack) != 0:\n                s[i] = ""\n                c = stack.pop()\n                s[c] = ""\n        s1 = "".join(s)\n        # Early ret -> no swap required\n        if len(s1) == 0:\n            return 0\n        s1 = list(s1)\n        left = 0\n        right = len(s1) - 1\n        swap = 0\n        while left < right:\n            s1[left], s1[right] = s1[right], s1[left]\n            swap += 1\n            left += 2\n            right -= 2\n        return swap\n        \n\n```
['Stack', 'Monotonic Stack', 'Python', 'Python3']