C++ ||  O(n) TIME AND SPACE || Apr 6 2024 Daily
Intuition\nThe problem involves removing the minimum number of parentheses from a string to make it a valid parentheses string. A valid parentheses string must 
# Intuition\nThe problem involves removing the minimum number of parentheses from a string to make it a valid parentheses string. A valid parentheses string must have balanced parentheses, meaning each opening parenthesis \'(\' must have a corresponding closing parenthesis \')\', and they must be properly nested. One might think of using a stack to keep track of the indices of opening parentheses and removing excess closing parentheses.\n\n# Approach\nThe provided code utilizes a stack to keep track of the indices of opening parentheses encountered in the string. It iterates through the string s character by character. Whenever an opening parenthesis \'(\' is encountered, its index is pushed onto the stack. If a closing parenthesis \')\' is encountered and the stack is empty, indicating there is no matching opening parenthesis, the closing parenthesis is marked for removal by replacing it with \'\'. Otherwise, the topmost index on the stack is popped, indicating that the current closing parenthesis matches with an opening parenthesis. After iterating through the entire string, any remaining opening parentheses on the stack are marked for removal by replacing them with \'\'. Finally, all \'*\' characters are removed from the string, and the resulting string is returned.\n\n# Complexity\n- Time complexity:\nO(n), where n is the length of the string s. The code iterates through the string once to process each character.\n\n- Space complexity:\nO(n), where n is the length of the string s. The space complexity arises from the stack, which can potentially store up to n/2 indices in the worst case if all characters are opening parentheses. Additionally, the code utilizes extra space to store the resulting string after removal of \'*\' characters.\n\n# Code\n```\nclass Solution {\npublic:\n    string minRemoveToMakeValid(string s) {\n        stack<int> stack;\n\n        for (int i = 0; i < s.length(); ++i)\n            if (s[i] == \'(\') {\n                stack.push(i);\n            } else if (s[i] == \')\') {\n                if (stack.empty())\n                    s[i] = \'*\';\n                else\n                    stack.pop();\n            }\n\n        while (!stack.empty())\n            s[stack.top()] = \'*\', stack.pop();\n\n        s.erase(remove(s.begin(), s.end(), \'*\'), s.end());\n        return s;\n    }\n};\n```
['String', 'Stack', 'C++']