STACK || Solution of minimum remove to make valid parentheses problem
This was a daily challenge for April 6th 2024.\n# Stack\nTo solve this problem we use the stack structure\n## Definition \nA stack is a linear data structure th
# This was a daily challenge for April 6th 2024.\n# Stack\n**To solve this problem we use the stack structure**\n## Definition \nA stack is a linear data structure that stores items in a Last-In/First-Out (LIFO) or First-In/Last-Out (FILO) manner. In stack, a new element is added at one end and an element is removed from that end only. The insert and delete operations are often called push and pop.\n## Usage\nThe functions associated with stack are:\n- `empty()` \u2013 Returns whether the stack is empty \u2013 Time Complexity: $$O(1)$$\n- `size()` \u2013 Returns the size of the stack \u2013 Time Complexity: $$O(1)$$\n- `top()` / `peek()` \u2013 Returns a reference to the topmost element of the stack \u2013 Time Complexity: $$O(1)$$\n- `pop()` \u2013 Deletes the topmost element of the stack \u2013 Time Complexity: $$O(1)$$\n# Approach\n- First step: \n**if current char is `"("`:** add `"("` to the stack and to the answer\n**if current char is `")"`:** if stack has `"("` then add `")"` to the answer and pop `"("` from the stack\n**if current char is not `"("` or `")"`:** add char to the answer\n- Second step:\nif stack has any amount of `"("` then replace them with `""`\n# Complexity\n- Time complexity:\n$$O(n)$$ - as loop takes linear time\n- Space complexity:\n$$O(n)$$ - as we use extra space for stack and answer \n\n# Code\n```\nclass Solution:\n    def minRemoveToMakeValid(self, s: str) -> str:\n        stack = []\n        answer = ""\n        for idx in range(len(s)):\n            if s[idx] == "(":\n                stack.append((s[idx], idx))\n                answer += s[idx]\n            elif s[idx] == ")":\n                if len(stack) > 0:\n                    stack.pop()\n                    answer += s[idx]\n            else:\n                answer += s[idx]\n        pre_answer = answer[::-1]\n        answer = pre_answer.replace(\'(\', \'\', len(stack))\n        return answer[::-1]\n\n```
['String', 'Stack', 'Python3']