# Minimum Add to Make Parentheses Valid
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-add-to-make-parentheses-valid)
Canonical: https://scaleengineer.com/dsa/problems/minimum-add-to-make-parentheses-valid
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String, Stack
**Companies:** [Nvidia](https://scaleengineer.com/companies/nvidia), [Siemens](https://scaleengineer.com/companies/siemens), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs)
---
## Problem
A parentheses string is valid if and only if:

* It is the empty string,
* It can be written as `AB` (`A` concatenated with `B`), where `A` and `B` are valid strings, or
* It can be written as `(A)`, where `A` is a valid string.

You are given a parentheses string `s`. In one move, you can insert a parenthesis at any position of the string.

* For example, if `s = "()))"`, you can insert an opening parenthesis to be `"(**(**)))"` or a closing parenthesis to be `"())**)**)"`.

Return _the minimum number of moves required to make_ `s` _valid_.

**Example 1:**

**Input:** s = "())"
**Output:** 1

**Example 2:**

**Input:** s = "((("
**Output:** 3

**Constraints:**

* `1 <= s.length <= 1000`
* `s[i]` is either `'('` or `')'`.

# Approaches
## Stack-based Simulation
This approach uses a stack, a common data structure for handling parenthesis matching problems. We iterate through the string, using the stack to keep track of unmatched opening parentheses. By analyzing the stack's state when we encounter a closing parenthesis and its final state after the loop, we can count the necessary additions.
**Time:** O(N), where N is the length of the string `s`. We perform a single pass through the string, and each stack operation (push, pop, isEmpty) takes constant time O(1). · **Space:** O(N), where N is the length of the string `s`. In the worst-case scenario, if the string consists of only opening parentheses like `((((...`, the stack will store all of them, leading to space usage proportional to the input string length.
**Pros:** It's an intuitive approach that directly models the pairing logic of parentheses.; The logic is easy to understand and is a standard technique for parenthesis-related problems.
**Cons:** Requires extra space for the stack, which can be up to O(N).; Slightly less efficient than the constant space approach due to memory overhead and function call overhead for stack operations.
### Explanation
We can simulate the process of matching parentheses using a stack. The core idea is that an opening parenthesis `(` is 'waiting' for a closing one `)`. The stack is a perfect tool to manage these 'waiting' parentheses.

For each character in the string:
- If we see an opening parenthesis `(`, we push it onto the stack. It will wait there until a matching `)` is found.
- If we see a closing parenthesis `)`, we check the stack. If the stack is not empty, we can pop an opening parenthesis, forming a valid pair `()`. If the stack is empty, it means this closing parenthesis has no preceding opening parenthesis to match with. This is an invalid state. To fix it, we must add an opening parenthesis. We count this as one required addition.

After iterating through the entire string, the stack may still contain some opening parentheses. These are the ones that never found a matching closing parenthesis. To make the string valid, each of these requires a closing parenthesis to be added. Therefore, the final number of additions is the count of additions for invalid `)` plus the number of `(` left in the stack.

```java
import java.util.Stack;

class Solution {
    public int minAddToMakeValid(String s) {
        Stack<Character> stack = new Stack<>();
        int additions = 0;

        for (char ch : s.toCharArray()) {
            if (ch == '(') {
                stack.push(ch);
            } else if (ch == ')') {
                if (stack.isEmpty()) {
                    // This ')' is unmatched, needs a '(' before it.
                    additions++;
                } else {
                    // Found a pair, pop the matching '('.
                    stack.pop();
                }
            }
        }

        // Any remaining '(' in the stack are unmatched.
        // They need a corresponding ')' to be added.
        additions += stack.size();

        return additions;
    }
}
```
### Algorithm
- Initialize an empty stack to store opening parentheses.
- Initialize a counter `additions` to 0.
- Iterate through each character of the input string `s`.
- If the character is an opening parenthesis `(`, push it onto the stack.
- If the character is a closing parenthesis `)`:
    - Check if the stack is empty. If it is, this `)` has no matching `(`. We must add an opening parenthesis to make it valid. Increment `additions`.
    - If the stack is not empty, it means there's a waiting `(`. We pop from the stack, signifying a successful match.
- After the loop finishes, any remaining parentheses in the stack are unmatched opening ones. Each of them requires a closing parenthesis to be added.
- The total minimum additions will be the current value of `additions` plus the final number of elements left in the stack.

## Single Pass with a Balance Counter
A more optimized approach avoids using a stack and instead relies on a simple counter to keep track of the balance between open and close parentheses. This method achieves the same result with constant extra space.
**Time:** O(N), where N is the length of the string `s`. We iterate through the string exactly once. · **Space:** O(1). We only use a few integer variables (`additions`, `balance`) to store our state, regardless of the input size.
**Pros:** Extremely efficient in terms of space, using only a constant amount of extra memory.; Very fast due to the simple single-pass logic with no overhead from complex data structures.
**Cons:** The logic might be slightly less intuitive at first glance compared to the direct simulation with a stack.
### Explanation
Instead of using a stack, we can solve this problem by iterating through the string just once while keeping track of the 'balance' of the string. The `balance` counter represents the number of open parentheses that are waiting for a closing one.

- We initialize `balance` and `additions` to zero.
- When we encounter an opening parenthesis `(`, we increment `balance` because we now have one more open parenthesis that needs a match.
- When we encounter a closing parenthesis `)`, we check the `balance`. 
    - If `balance` is greater than 0, it means there's an open parenthesis waiting. We can use this `)` to form a pair, so we decrement `balance`.
    - If `balance` is 0, it means there are no open parentheses waiting for a match. This `)` is therefore invalid. To make it valid, we must insert an opening parenthesis. We count this by incrementing `additions`.

After the loop, the `balance` counter holds the number of opening parentheses that were never closed. To make the string valid, we need to add a closing parenthesis for each of these. So, the total number of additions is the `additions` we've counted so far, plus the final value of `balance`.

For example, with `s = "()))((`:
- `(`: `balance` becomes 1.
- `)`: `balance` becomes 0.
- `)`: `balance` is 0, so `additions` becomes 1.
- `(`: `balance` becomes 1.
- `(`: `balance` becomes 2.
- End of loop. Total additions = `additions` + `balance` = 1 + 2 = 3.

```java
class Solution {
    public int minAddToMakeValid(String s) {
        int additions = 0;
        int balance = 0;

        for (char ch : s.toCharArray()) {
            if (ch == '(') {
                balance++;
            } else if (ch == ')') {
                if (balance > 0) {
                    balance--;
                } else {
                    // This ')' has no matching '('.
                    // We need to add a '(' to make it valid.
                    additions++;
                }
            }
        }

        // After the loop, 'balance' is the number of unmatched '('.
        // We need to add 'balance' number of ')' to make them valid.
        additions += balance;

        return additions;
    }
}
```
### Algorithm
- Initialize two counters: `additions = 0` and `balance = 0`.
- Iterate through each character of the input string `s`.
- If the character is `(`, it increases the number of unmatched open parentheses, so we increment `balance`.
- If the character is `)`:
    - If `balance > 0`, it means there's an unmatched `(` available to be paired. We decrement `balance`.
    - If `balance == 0`, this `)` has no preceding `(`. It's an invalid parenthesis. We need to add one `(` to fix it. So, we increment `additions`.
- After iterating through the entire string, if `balance` is still positive, it represents the number of unmatched `(` at the end of the string. Each of these requires a `)` to be added.
- The total minimum additions is the sum of `additions` (for invalid `)`) and the final `balance` (for unmatched `(`).

# Solutions
### Java

```java
class Solution {
public
  int minAddToMakeValid(String s) {
    int ans = 0, cnt = 0;
    for (char c : s.toCharArray()) {
      if (c == '(') {
        ++cnt;
      } else if (cnt > 0) {
        --cnt;
      } else {
        ++ans;
      }
    }
    ans += cnt;
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minAddToMakeValid(string s) {
    int ans = 0, cnt = 0;
    for (char c : s) {
      if (c == '(')
        ++cnt;
      else if (cnt)
        --cnt;
      else
        ++ans;
    }
    ans += cnt;
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minAddToMakeValid(self, s: str) -> int: ans = cnt = 0 for c in s: if c == '(': cnt += 1 elif cnt: cnt -= 1 else: ans += 1 ans += cnt return ans

```