100% Beat | Easy 2 Approaches Stack & Without Stack || Detailed Explanation
Note: Code is Re Formatted using chatgpt for bettter Comments and variable names so that you can better understand..\n# Personal opinion\nLeetcode is trying to 
*Note: Code is Re Formatted using chatgpt for bettter Comments and variable names so that you can better understand..*\n# Personal opinion\nLeetcode is trying to teach us Stack DS so before doing this you should try the daily problem of day before yesterday\nhttps://leetcode.com/problems/maximum-nesting-depth-of-the-parentheses/description/ and then yesterday \nhttps://leetcode.com/problems/make-the-string-great/description/\nand then this problem. \ni hope next day we will get another problem of stack DS.\n# Intuition\n![Screenshot 2024-04-06 053717.png](https://assets.leetcode.com/users/images/c3537a8d-aaba-4625-a0a2-c67c543bfefa_1712364006.160108.png)\n<!-- Describe your first thoughts on how to solve this problem. -->\nImagine a shoe store where each customer needs a matching pair of shoes.\n\n**Preparing:**\n\n- The store manager sets up empty shelves for left and right shoes (startPart and endPart).\n- They get a list of all customers\' shoe requests (char[] arr).\n- They have a counter to track the number of customers who still need a left shoe (openParenthesesCount).\n\n**First Pass: Finding Extra Right Shoes:**\n\n- The manager goes through the list one customer at a time.\n- If a customer needs a left shoe (arr[i] == \'(\'), they increase the counter.\n- If a customer needs a right shoe (`arr[i] == \')\'), they check:\n- If no customers need left shoes (openParenthesesCount == 0), the right shoe is extra (arr[i] = \'*\'). They mark it for return.\n- If there are customers needing left shoes, a pair is made, and the counter goes down.\n\n**Second Pass: Finding Extra Left Shoes:**\n\n- The manager starts from the end of the list, looking for extra left shoes.\n- If a customer needs a left shoe (arr[i] == \'(\') and there are still customers needing right shoes (openParenthesesCount > 0), the left shoe is extra. They mark it for return.\n\n **Arranging the Shelves:**\n\n- The manager takes all non-marked shoes (arr[i] != \'*\') and puts them neatly on the shelves.\n\n**Displaying the Shoes:**\n\n- They beautifully display the matching pairs from the shelves (result).\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**Initialization:**\n- Initialize pointers for the start and end of the string, variables to store the start and end parts of the string, and the final result. Convert the input string into a character array for easier manipulation.\n\n**First Pass:** \n- Iterate through the string from left to right. Track the count of open parentheses encountered. If an excess closing parenthesis is encountered (i.e., a closing parenthesis with no matching opening parenthesis), mark it with \'*\'. Keep track of the count of open parentheses encountered.\n\n**Second Pass:** \n- Iterate through the string from right to left. If there are excess opening parentheses remaining (i.e., opening parentheses with no matching closing parenthesis), mark them with \'*\'.\n\n**Filtering:** \n- Filter out the marked characters (\'*\') from the character array, leaving only the valid parentheses.\n\n**Construct Result:** \n- Construct the result string from the filtered character array.\n\n**Return Result:** \n- Return the final result string, which contains the minimum number of parentheses required to make the input string valid.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n\n# Approach -1  Without Stack\n```java []\n\nclass Solution {\n    public String minRemoveToMakeValid(String s) {\n        // Initialize pointers for the start and end of the string\n        int startPointer = 0;\n        int endPointer = s.length() - 1;\n\n        String result;\n\n        // Convert input string to character array for easier manipulation\n        char[] arr = s.toCharArray();\n        \n        // Counter for open parentheses\n        int openParenthesesCount = 0;\n\n        // First pass: mark excess closing parentheses with \'*\'\n        for (int i = 0; i < arr.length; i++) {\n            if (arr[i] == \'(\')\n                openParenthesesCount++;\n            else if (arr[i] == \')\') {\n                if (openParenthesesCount == 0)\n                    arr[i] = \'*\'; // Mark excess closing parentheses\n                else\n                    openParenthesesCount--;\n            }\n        }\n\n        // Second pass: mark excess opening parentheses from the end\n        for (int i = arr.length - 1; i >= 0; i--) {\n            if (openParenthesesCount > 0 && arr[i] == \'(\') {\n                arr[i] = \'*\'; // Mark excess opening parentheses\n                openParenthesesCount--;\n            }\n        }\n        \n        // Filter out marked characters and store the result in the character array\n        int p = 0; // Pointer for updating the character array\n        for (int i = 0; i < arr.length; i++) {\n            if (arr[i] != \'*\')\n                arr[p++] = arr[i];\n        }\n\n        // Construct the result string from the filtered character array\n        result = new String(arr).substring(0, p);\n\n        return result;\n    }\n}\n```\n```C++ []\n\nclass Solution {\npublic:\n    string minRemoveToMakeValid(string s) {\n        // Initialize variables\n        int openParenthesesCount = 0;\n        vector<char> arr(s.begin(), s.end()); // Convert string to character array\n\n        // First pass: mark excess closing parentheses with \'*\'\n        for (int i = 0; i < arr.size(); i++) {\n            if (arr[i] == \'(\')\n                openParenthesesCount++;\n            else if (arr[i] == \')\') {\n                if (openParenthesesCount == 0)\n                    arr[i] = \'*\'; // Mark excess closing parentheses\n                else\n                    openParenthesesCount--;\n            }\n        }\n\n        // Second pass: mark excess opening parentheses from the end\n        for (int i = arr.size() - 1; i >= 0; i--) {\n            if (openParenthesesCount > 0 && arr[i] == \'(\') {\n                arr[i] = \'*\'; // Mark excess opening parentheses\n                openParenthesesCount--;\n            }\n        }\n        \n        // Filter out marked characters and store the result in a new string\n        string result = "";\n        for (char c : arr) {\n            if (c != \'*\')\n                result += c;\n        }\n\n        return result;\n    }\n};\n\n```\n```Python []\nclass Solution:\n    def minRemoveToMakeValid(self, s: str) -> str:\n        # Initialize variables\n        openParenthesesCount = 0\n        arr = list(s)\n\n        # First pass: mark excess closing parentheses with \'*\'\n        for i in range(len(arr)):\n            if arr[i] == \'(\':\n                openParenthesesCount += 1\n            elif arr[i] == \')\':\n                if openParenthesesCount == 0:\n                    arr[i] = \'*\' # Mark excess closing parentheses\n                else:\n                    openParenthesesCount -= 1\n\n        # Second pass: mark excess opening parentheses from the end\n        for i in range(len(arr) - 1, -1, -1):\n            if openParenthesesCount > 0 and arr[i] == \'(\':\n                arr[i] = \'*\' # Mark excess opening parentheses\n                openParenthesesCount -= 1\n        \n        # Filter out marked characters and construct the result string\n        result = \'\'.join(c for c in arr if c != \'*\')\n\n        return result\n\n```\n\n# Approach -2 With Stack\n```java []\nclass Solution {\n    public String minRemoveToMakeValid(String s) {\n        // Initialize counts for left and right parentheses\n        int leftCount = 0;\n        int rightCount = 0;\n\n        // Use a stack to keep track of valid parentheses\n        Stack<Character> stack = new Stack<>();\n\n        // Pass 1: Iterate through the string and process parentheses\n        for (int i = 0; i < s.length(); i++) {\n            char currentChar = s.charAt(i);\n\n            // Increment count for left parentheses\n            if (currentChar == \'(\') {\n                leftCount++;\n            }\n            // Increment count for right parentheses\n            if (currentChar == \')\') {\n                rightCount++;\n            }\n\n            // If there are more right parentheses than left, skip the current right parenthesis\n            if (rightCount > leftCount) {\n                rightCount--; // Decrease right count\n                continue;     // Skip processing this right parenthesis\n            } else {\n                stack.push(currentChar); // Add valid parentheses to the stack\n            }\n        }\n\n        // Pass 2: Reconstruct the string using the valid parentheses in the stack\n        StringBuilder result = new StringBuilder();\n        while (!stack.isEmpty()) {\n            char currentChar = stack.pop();\n            // If there are more left parentheses than right, skip the current left parenthesis\n            if (leftCount > rightCount && currentChar == \'(\') {\n                leftCount--; // Decrease left count\n                // Do nothing, skip this left parenthesis\n            } else {\n                result.append(currentChar); // Add valid parentheses to the result\n            }\n        }\n\n        // Reverse the result string and return\n        return result.reverse().toString();\n    }\n}\n\n```\n```python []\nclass Solution:\n    def minRemoveToMakeValid(self, s: str) -> str:\n        left_count = 0\n        right_count = 0\n        stack = []\n\n        # Pass 1\n        for ch in s:\n            if ch == \'(\':\n                left_count += 1\n            elif ch == \')\':\n                right_count += 1\n            if right_count > left_count:\n                right_count -= 1\n            else:\n                stack.append(ch)\n\n        result = ""\n\n        # Pass 2\n        while stack:\n            current_char = stack.pop()\n            if left_count > right_count and current_char == \'(\':\n                left_count -= 1\n            else:\n                result += current_char\n\n        # Reverse the result string\n        return result[::-1]\n\n```\n```C++ []\n\nclass Solution {\npublic:\n    std::string minRemoveToMakeValid(std::string s) {\n        int leftCount = 0;\n        int rightCount = 0;\n        std::stack<char> stack;\n\n        // Pass 1\n        for (char ch : s) {\n            if (ch == \'(\') {\n                leftCount++;\n            } else if (ch == \')\') {\n                rightCount++;\n            }\n            if (rightCount > leftCount) {\n                rightCount--;\n                continue;\n            } else {\n                stack.push(ch);\n            }\n        }\n\n        std::string result = "";\n        \n        // Pass 2\n        while (!stack.empty()) {\n            char currentChar = stack.top();\n            stack.pop();\n            if (leftCount > rightCount && currentChar == \'(\') {\n                leftCount--;\n            } else {\n                result += currentChar;\n            }\n        }\n\n        // Reverse the result string\n        std::reverse(result.begin(), result.end());\n        return result;\n    }\n};\n```\n\n\n![main-qimg-dd19ad82f9afcc414cdfc8ded048648e-lq.jpeg](https://assets.leetcode.com/users/images/62dab831-a932-4ddc-9be7-835369753c83_1712362226.866529.jpeg)\n
['Python', 'C++', 'Java', 'Python3']