[Beats 100%🔥] 2 Solutions Brute & Optimized | Beginner Friendly Explanation🚀
Solution 1️⃣ :Intuitionwe can track unmatched opening and closing brackets.
Key observation:A valid sequence maintains a balance between opening and closing bra
# Solution 1️⃣ :
# Intuition
we can track unmatched opening and closing brackets.  
- **Key observation:** A valid sequence maintains a balance between opening and closing brackets.  
- Instead of checking pairs manually, use a **stack** to track unmatched opening brackets.  
- Every unmatched closing bracket directly contributes to the required additions.
# Approach
- Use a **stack** to track unmatched `(`.
- Traverse the string:
  - If `(`, push it onto the stack.
  - If `)`, check if there's a matching `(` in the stack.
    - If yes, pop `(`.
    - If no, increment `count` (indicating an unmatched `)`).
- The result is the sum of `count` (unmatched `)`) and `stack.size()` (remaining unmatched `(`).

# Complexity
- **Time Complexity:** $$O(n)$$ (single pass)
- **Space Complexity:** $$O(n)$$ (stack usage in worst case)


# Code
```java []
class Solution {
    public int minAddToMakeValid(String s) {
        Stack<Character> stack = new Stack<>();
        int count = 0; // Tracks unmatched closing brackets

        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(c); // Push opening bracket
            } else {   
                if (stack.isEmpty()) {
                    count++; // No matching '(', so increment unmatched count
                } else {
                    stack.pop(); // Match found, pop from stack
                }
            }
        }

        // Remaining unmatched '(' + unmatched ')'
        return count + stack.size(); 
    }
}

```

# Solution 2️⃣:

# Intuition
To determine the minimum additions needed to make a parentheses string valid, we can use a counter approach instead of a stack. Track unmatched opening and closing brackets separately.

# Approach
1. Use two counters:
   - `l` for unmatched opening brackets `(`.
   - `r` for unmatched closing brackets `)`.
2. Traverse the string:
   - If `(` is found, increment `l`.
   - If `)` is found:
     - If `l > 0`, decrement `l` (valid pair found).
     - Else, increment `r` (extra `)` found).
3. The result is `l + r`, representing the unmatched parentheses that need to be added.

# Complexity
- **Time Complexity:** $$O(n)$$  
- **Space Complexity:** $$O(1)$$  

``` Java []
class Solution {
  public int minAddToMakeValid(String s) {
    int l = 0; // Tracks unmatched '('
    int r = 0; // Tracks unmatched ')'

    // Iterate through each character in the string
    for (final char c : s.toCharArray()) {
      if (c == '(') {
        ++l; // Increment count of '('
      } else {   
        if (l == 0) // If there's no unmatched '(' to pair with ')'
          ++r; // Count this ')' as unmatched
        else
          --l; // Match this ')' with a previous '('
      }
    }

    return l + r; // Sum of unmatched '(' and ')'
  }
}
```
**Please Upvote⬆️**
![Screenshot 2025-02-15 134751.png](https://assets.leetcode.com/users/images/3c5bb34f-0d5b-41dc-a192-d44fbd6d3072_1740229882.7060237.png)

['String', 'Stack', 'Greedy', 'Counting', 'Java']