Easy Solution with Explanation 🔥🔥🔥 | Beats 96.23% 🔥🔥🔥 | Python | Python3
Intuition\n Describe your first thoughts on how to solve this problem. \nThe core idea here is to make sure every opening parenthesis \'(\' finds a matching clo
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe core idea here is to make sure every opening parenthesis \'(\' finds a matching closing parenthesis \')\' and vice versa. However, if there\'s an imbalance\u2014too many opening or closing parentheses\u2014we need to remove the minimum number to correct this imbalance. We focus on ensuring the string becomes valid by having each parenthesis pair properly matched from left to right.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nTrack Open Parentheses: We use a stack to keep track of parentheses as we scan through the string. The stack helps us understand the current state of open and closed parentheses.\nScan and Build: As we go through each character in the string:\n- If it\'s an opening parenthesis \'(\', we add it to the stack and note that we have one more unmatched \'(\'.\n- If it\'s a closing parenthesis \')\', we check if we have an unmatched \'(\' earlier. If we do, this \')\' is a valid match, and we add it to the stack. \n- If not, we ignore this \')\' because it doesn\'t have a pair.\n- For any other character, we just add it to the stack since they don\'t affect the validity of the parentheses.\n\nRemove Excess Opening Parentheses: After the first pass, we might have some \'(\' left without a match. We then make a backward pass through the stack to remove these excess \'(\' characters, ensuring we don\'t leave any unmatched \'(\'.\n\nReconstruct the String: Finally, we join the characters left in the stack to form the modified string, which now has valid parentheses.\n\n\n# Complexity\nTime complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- O(N): We traverse the string twice\u2014once to build the stack and once to remove any unmatched \'(\'. Since each pass is linear with respect to the length of the string (N), the overall time complexity is linear.\n\n\nSpace complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n- O(N): In the worst case, we might need to store all characters of the string in the stack (for example, if all characters are opening parentheses). Thus, the space complexity is linear with respect to the input string\'s length.\n\n# Code\n```\nclass Solution:\n    def minRemoveToMakeValid(self, s: str) -> str:\n        stack = []  # Keep track of valid characters.\n        array = list(s) \n\n        paranthesisCount = 0  # Number of open parentheses.\n\n        for char in array:\n            if char == \'(\':\n                # If the char is (, increment the count and add it to the stack.\n                paranthesisCount += 1\n                stack.append(char)\n            elif char == \')\':\n                # If the char is a ), check if there is an unmatched open parenthesis.\n                if paranthesisCount > 0:\n                    # If there is, decrement the count and add the closing parenthesis to the stack.\n                    paranthesisCount -= 1\n                    stack.append(char)\n                else:\n                    # If there isn\'t, ignore this closing parenthesis as it\'s invalid.\n                    continue\n            else:\n                # If the character is not a parenthesis, add it to the stack as it is.\n                stack.append(char)\n        \n        # Now, we need to remove any unmatched open parentheses from the stack.\n        # We iterate in reverse to start from the end of the string.\n        for i in range(len(stack)-1, -1, -1):\n            if paranthesisCount > 0 and stack[i] == \'(\':\n                # If we still have unmatched open parentheses, remove them from the stack.\n                stack.pop(i)\n                paranthesisCount -= 1\n        \n        # Convert the stack back to a string and return it.\n        return \'\'.join(stack)\n\n```
['Stack', 'Python', 'Python3']