[Beats 100%🔥] Stack Approach | Beginner Friendly🚀
IntuitionTo determine how to make the string valid with minimal removals, we need to identifyunmatched parentheses.
Using astackis a natural choice, as it allow
# Intuition
To determine how to make the string valid with minimal removals, we need to identify **unmatched parentheses**.  
- Using a **stack** is a natural choice, as it allows us to track unmatched opening parentheses `(`.  
- When encountering `)`, we check if there's a matching `(` in the stack. If not, it's unmatched and should be removed.  
- Any leftover `(` in the stack after processing the string are also unmatched and should be removed.

# Approach
1. **First Pass:**  
   - Iterate through the string and use a stack to store indices of unmatched `(`.  
   - If `)` appears and no matching `(` exists, mark it for removal.  
2. **Second Pass:**  
   - Remove remaining unmatched `(` from the stack.  
3. **Final Step:**  
   - Construct the valid string by removing marked characters.

# Complexity
- **Time Complexity:** $$O(n)$$  
- **Space Complexity:** $$O(n)$$  
# Code
```java []
class Solution {
    public String minRemoveToMakeValid(String s) {
        Stack<Integer> stack = new Stack<>();
        StringBuilder valid = new StringBuilder(s);

        // First pass to find unmatched closing parentheses ')'
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);  // Push index of '(' onto the stack
            } else if (s.charAt(i) == ')') {
                if (stack.isEmpty()) {
                    valid.setCharAt(i, ' ');  // Mark unmatched ')' as ' '
                } else {
                    stack.pop();  // Valid match found, pop '(' from stack
                }
            }
        }

        // Second pass to remove unmatched opening parentheses '('
        while (!stack.isEmpty()) {
            valid.setCharAt(stack.pop(), ' ');  // Mark unmatched '(' as ' '
        }

        // Remove all spaces (marked invalid characters)
        return valid.toString().replace(" ", "");
    }
}

```

**Please Upvote⬆️**

![Screenshot 2025-02-15 134751.png](https://assets.leetcode.com/users/images/61147721-645c-4480-8985-15b01a4873dd_1740232442.9661481.png)

['String', 'Stack', 'Java']