# Minimum Insertions to Balance a Parentheses String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-insertions-to-balance-a-parentheses-string)
Canonical: https://scaleengineer.com/dsa/problems/minimum-insertions-to-balance-a-parentheses-string
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String, Stack
**Companies:** [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan)
---
## Problem
Given a parentheses string `s` containing only the characters `'('` and `')'`. A parentheses string is **balanced** if:

* Any left parenthesis `'('` must have a corresponding two consecutive right parenthesis `'))'`.
* Left parenthesis `'('` must go before the corresponding two consecutive right parenthesis `'))'`.

In other words, we treat `'('` as an opening parenthesis and `'))'` as a closing parenthesis.

* For example, `"())"`, `"())(())))"` and `"(())())))"` are balanced, `")()"`, `"()))"` and `"(()))"` are not balanced.

You can insert the characters `'('` and `')'` at any position of the string to balance it if needed.

Return _the minimum number of insertions_ needed to make `s` balanced.

**Example 1:**

**Input:** s = "(()))"
**Output:** 1
**Explanation:** The second '(' has two matching '))', but the first '(' has only ')' matching. We need to add one more ')' at the end of the string to be "(())))" which is balanced.

**Example 2:**

**Input:** s = "())"
**Output:** 0
**Explanation:** The string is already balanced.

**Example 3:**

**Input:** s = "))())("
**Output:** 3
**Explanation:** Add '(' to match the first '))', Add '))' to match the last '('.

**Constraints:**

* `1 <= s.length <= 105`
* `s` consists of `'('` and `')'` only.

# Approaches
## Single Pass with Lookahead
This approach iterates through the string while maintaining a count of open parentheses that need to be closed. When a right parenthesis `')'` is encountered, we look at the next character to decide if we have a `'))'` pair or a single `')'`. Based on this, we update the count of open parentheses and the number of insertions needed.
**Time:** O(N), where N is the length of the string `s`. We iterate through the string only once. · **Space:** O(1) extra space, as we only use a few integer variables to keep track of counts, regardless of the input string size.
**Pros:** Correct and efficient, solving the problem in a single pass.; Utilizes constant extra space, making it memory-efficient.
**Cons:** The logic is slightly more complex due to the need for lookahead and handling two separate cases for right parentheses (`')'` vs `'))'`).; The code can be less intuitive to follow because of the nested conditional statements and manual index management.
### Explanation
This approach solves the problem by performing a single pass through the input string. It uses a counter, `openNeeded`, to keep track of the number of `'('` characters that are waiting for a corresponding `''))'` closing pair. The core of the logic involves checking for `'))'` pairs versus single `')'` characters and updating the counts accordingly.

When a `'('` is found, we simply increment `openNeeded`. When a `')'` is found, we look ahead. If the next character is also a `')'`, we treat them as a `'))'` pair. This pair can satisfy one `openNeeded` requirement. If there are no open parentheses needing to be closed (`openNeeded == 0`), we must insert a `'('`, incrementing our `insertions` count. If we only find a single `')'`, we know we must insert another `')'` to form a `'))'` pair. After this conceptual insertion, we proceed as if we found a `'))'` pair.

Finally, after iterating through the entire string, any remaining `openNeeded` count signifies open parentheses that were never closed. Each of these requires two `')'` insertions to form a `'))'` pair.

```java
class Solution {
    public int minInsertions(String s) {
        int insertions = 0;
        int openNeeded = 0;
        int i = 0;
        while (i < s.length()) {
            if (s.charAt(i) == '(') {
                openNeeded++;
                i++;
            } else { // s.charAt(i) == ')'
                // Check for a ')' pair
                if (i + 1 < s.length() && s.charAt(i + 1) == ')') {
                    if (openNeeded > 0) {
                        openNeeded--;
                    } else {
                        // This '))' needs a preceding '('
                        insertions++;
                    }
                    i += 2;
                } else {
                    // This is a single ')'
                    // Step 1: We need to insert one ')' to make a pair.
                    insertions++;
                    // Step 2: Now we have a '))' pair. Check if it can close an open '('
                    if (openNeeded > 0) {
                        openNeeded--;
                    } else {
                        // This new '))' also needs a preceding '('
                        insertions++;
                    }
                    i++;
                }
            }
        }

        // Any remaining open brackets need two ')' each.
        insertions += openNeeded * 2;
        return insertions;
    }
}
```
### Algorithm
- Initialize `insertions = 0` and `open_needed = 0`.
- Iterate through the string `s` with an index `i`.
- If `s[i]` is `'('`:
    - Increment `open_needed`.
- If `s[i]` is `')'`:
    - Check if `i+1` is within bounds and `s[i+1]` is also `')'`.
    - If yes (we have a `''))'` pair):
        - If `open_needed > 0`, it means this pair can close an existing open parenthesis. Decrement `open_needed`.
        - If `open_needed == 0`, this pair is unmatched. We need to insert a `'('` before it. Increment `insertions`.
        - Increment `i` to skip the next `')'`.
    - If no (we have a single `')'`):
        - This single `')'` must be part of a `''))'` pair. We need to insert another `')'`. Increment `insertions`.
        - Now that we have a conceptual `''))'` pair, we check if it can close an open parenthesis.
        - If `open_needed > 0`, decrement `open_needed`.
        - If `open_needed == 0`, we also need to insert a `'('`. Increment `insertions` again.
- After the loop, there might be some remaining `open_needed`. Each requires a `''))'` pair for closing.
- Add `open_needed * 2` to `insertions`.
- Return `insertions`.

## Optimized Single Pass with a Balance Counter
This is a more streamlined single-pass approach. Instead of counting open parentheses, we maintain a "balance" counter, let's call it `right_needed`, which represents the number of right parentheses `')'` we currently need to see to keep the string balanced. This simplifies the logic by elegantly handling all cases in a unified manner without explicit lookahead.
**Time:** O(N), where N is the length of the string `s`. The algorithm involves a single pass over the string. · **Space:** O(1) extra space. Only a constant number of integer variables are used.
**Pros:** Optimal time and space complexity.; The logic is more elegant and concise compared to the lookahead approach.; It handles all cases smoothly within a single loop structure without manual index management.
**Cons:** The logic behind the `right_needed` counter, especially the updates for odd values and when it becomes negative, can be subtle and requires careful thought to understand correctly.
### Explanation
This optimized approach uses a single counter, `rightNeeded`, to track the balance of the parentheses. This counter represents the number of `')'` characters we expect to see to balance the parentheses encountered so far. This method avoids explicit lookahead and simplifies the code.

The logic is as follows:
- When we see a `'('`, we will need two `')'` characters in the future, so we increment `rightNeeded` by 2. However, if `rightNeeded` was odd before this, it means there was a lone `')'` waiting for a partner. We must first insert a `')'` to complete that pair (costing 1 insertion), which in turn closes a pending `'('` (decrementing `rightNeeded` by 1).
- When we see a `')'`, it fulfills one of the needed right parentheses, so we decrement `rightNeeded`. If `rightNeeded` drops to -1, it means we have an excess `')'` without a preceding `'('`. We must insert a `'('` (costing 1 insertion). This new `'('` now requires a `'))'` pair. Since we have the current `')'`, our `rightNeeded` becomes 1.
- After the loop, any remaining value in `rightNeeded` represents the number of `')'` we must append to the end to close all remaining open parentheses.

```java
class Solution {
    public int minInsertions(String s) {
        int insertions = 0;
        int rightNeeded = 0; // Tracks the number of ')' needed

        for (char c : s.toCharArray()) {
            if (c == '(') {
                // If rightNeeded is odd, it means we have a single ')' that needs a partner.
                // We must insert one ')' to make ')).' This ')),' will close a pending '('.
                if (rightNeeded % 2 != 0) {
                    insertions++; // Insert one ')'
                    rightNeeded--;  // One '(' is now balanced
                }
                // The current '(' needs two ')'
                rightNeeded += 2;
            } else { // c == ')'
                // We encountered a ')', so our need for ')' decreases.
                rightNeeded--;
                // If rightNeeded becomes negative, we have an excess ')'.
                // We need to insert a '(' to match it.
                if (rightNeeded < 0) {
                    insertions++; // Insert one '('
                    // This new '(' also needs a '))'. We have one ')', so we need one more.
                    // So, rightNeeded goes from -1 to 1.
                    rightNeeded += 2; 
                }
            }
        }

        // After iterating, rightNeeded is the number of ')' we still need to insert.
        insertions += rightNeeded;
        return insertions;
    }
}
```
### Algorithm
- Initialize `insertions = 0` and `right_needed = 0`.
- Iterate through each character `c` of the string `s`.
- If `c` is `'('`:
    - If `right_needed` is odd, it implies we have a single, unmatched `')'` from before. To fix this, we must insert one `')'` to form a `''))'` pair. This pair will close a previously opened `'('`. So, we increment `insertions` and decrement `right_needed`.
    - The current `'('` requires a `''))'` pair. So, we add 2 to `right_needed`.
- If `c` is `')'`:
    - This `')'` helps satisfy our requirement. Decrement `right_needed`.
    - If `right_needed` becomes negative, it means we have an excess `')'` without a matching `'('`. We must insert a `'('`. This increments `insertions`. The newly inserted `'('` itself requires a `''))'` pair. We have the current `')'`, so we now need one more `')'`. This means `right_needed` should be 1 (effectively, `right_needed` goes from -1 to 1, which is `right_needed += 2`).
- After the loop, `right_needed` holds the count of `')'` characters that are still required to balance the string.
- Add `right_needed` to `insertions`.
- Return `insertions`.

# Solutions
### Java

```java
class Solution {
public
  int minInsertions(String s) {
    int ans = 0, x = 0;
    int n = s.length();
    for (int i = 0; i < n; ++i) {
      if (s.charAt(i) == '(') {
        ++x;
      } else {
        if (i < n - 1 && s.charAt(i + 1) == ')') {
          ++i;
        } else {
          ++ans;
        }
        if (x == 0) {
          ++ans;
        } else {
          --x;
        }
      }
    }
    ans += x << 1;
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minInsertions(string s) {
    int ans = 0, x = 0;
    int n = s.size();
    for (int i = 0; i < n; ++i) {
      if (s[i] == '(') {
        ++x;
      } else {
        if (i < n - 1 && s[i + 1] == ')') {
          ++i;
        } else {
          ++ans;
        }
        if (x == 0) {
          ++ans;
        } else {
          --x;
        }
      }
    }
    ans += x << 1;
    return ans;
  }
};

```

### Python

```python
class Solution:
    # 待匹配的左括号加 1 x += 1 else : if i < n - 1 and s [ i + 1 ] == ')' : # 有连续两个右括号，i 往后移动 i += 1 else : # 只有一个右括号，插入一个 ans += 1 if x == 0 : # 无待匹配的左括号，插入一个 ans += 1 else : # 待匹配的左括号减 1 x -= 1 i += 1 # 遍历结束，仍有待匹配的左括号，说明右括号不足，插入 x << 1 个 ans += x << 1 return ans
    def minInsertions(self, s: str) -> int: ans = x = 0 i, n = 0, len(s) while i < n: if s[i] == '(':

```