Insert the Fewest Parentheses to Make a String Balanced
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
A valid parentheses string is empty, a concatenation of two valid strings, or a valid string enclosed in one matching pair. Given `s`, insert one opening or closing parenthesis anywhere per move. Return the minimum number of insertions needed to make the complete string valid.
```cpp
class Solution {
public:
int minAddToMakeValid(string s);
};
```
### Examples
**Example 1:**
```text
Input: s = ")()("
Output: 2
Explanation: The first closing parenthesis needs an opening one before it, and the last opening parenthesis needs a closing one after it.
```
**Example 2:**
```text
Input: s = "(()())"
Output: 0
Explanation: Every prefix has enough openings and the total counts balance.
```
### Constraints
- `1 <= s.length <= 1000`.
- Every character is `(` or `)`.
### Contract considerations
The answer counts inserted characters, not a replacement string or a number of swaps.
```hint Read the boundary condition
When a closing parenthesis has no available opening, no later original opening can match it.
```
### Boundary reminders
The answer counts inserted characters, not a replacement string or a number of swaps.
Overview: Insert the Fewest Parentheses to Make a String Balanced. A valid parentheses string is empty, a concatenation of two valid strings, or a valid string enclosed in one matching pair.