The algorithm works as follows:

1. Scan the string for the substring "()".
2. If found, remove it from the string.
3. Repeat step 1 until no "()" substrings remain.
4. The length of the remaining string is the answer (since all remaining characters are unmatched and require a partner).

python
# Pseudo-code for Brute Force
while "()" in s:
    s = s.replace("()", "")
return len(s)

Complexity Analysis:

• Time Complexity: $O(N^2)$. In the worst case (e.g., ((...))), we might iterate through the string $N/2$ times, and each string replacement operation takes $O(N)$ time.
• Why it fails: While $N=1000$ might pass within time limits for this specific problem, this approach is algorithmically inefficient. It modifies the string repeatedly, leading to quadratic time complexity, which would fail on larger inputs typical of production environments or harder interview constraints.

Core Insight for Minimum Add to Make Parentheses Valid

The core intuition is that every valid pair () cancels itself out. We can process the string linearly, maintaining a record of "open" expectations.

When we encounter an opening bracket (, we don't know yet if it will be valid. We push it onto a stack (or a waiting list) effectively saying, "I need a closing bracket."

When we encounter a closing bracket ), we check our most recent expectation:

1. Match Found: If the most recent unmatched character was (, we have found a valid pair. We remove the ( from our record (pop from stack). The pair is now resolved and contributes nothing to the final "add" count.
2. No Match: If there are no pending ( characters (the stack is empty or contains only unmatched )), this ) is unmatched. We record it as needing an opening partner.

By the end of the traversal, the stack will contain only the characters that never found a match. The size of this stack is exactly the number of insertions needed.

Visual Description: Imagine iterating through s = "())".

• Index 0: (. Push to stack. Stack: ['('].
• Index 1: ). Matches top (. Pop. Stack: [].
• Index 2: ). Stack empty. Push ). Stack: [')'].
• End: Stack size is 1. We need 1 addition.

Execution Flow

Let's trace the algorithm with the input s = "())(".

1. Initialize: stack = []
2. Process index 0: `char = '(':
   • Push ( onto stack.
   • State: stack = ['(']
3. Process index 1: char = ')':
   • Check stack top. It is (. Match found.
   • Pop (.
   • State: stack = []
4. Process index 2: char = ')':
   • Check stack top. Stack is empty. No match.
   • Push ) onto stack.
   • State: stack = [')']
5. Process index 3: `char = '(':
   • Push ( onto stack.
   • State: stack = [')', '(']
6. End of String:
   • The stack has 2 elements: ')' and '('.
   • This means we have one unmatched closing bracket and one unmatched opening bracket.
   • Result: 2 (We need to add ( at the start and ) at the end).

Proof of Correctness

The correctness relies on the invariant that the stack only contains unmatched parentheses in their original relative order.

• When a ) encounters a (, they form a valid pair and are removed. This is a safe greedy move because the inner-most pair must be resolved first in any valid parentheses expression.
• Any ) that enters the stack does so because there was no available ( to match it.
• Any ( that remains in the stack does so because no subsequent ) appeared to match it.
• Therefore, the final stack size represents exactly the count of characters that violate the validity condition. Each requires exactly one insertion to become valid.

Reference Implementation

C++ Solution for LeetCode 921

cpp
class Solution {
public:
    int minAddToMakeValid(string s) {
        // Stack to store unmatched parentheses
        vector<char> stack;
        
        for (char c : s) {
            // If we encounter a closing bracket and the stack has an opening bracket
            if (c == ')' && !stack.empty() && stack.back() == '(') {
                stack.pop_back(); // Match found, resolve the pair
            } else {
                stack.push_back(c); // No match, push to stack
            }
        }
        
        // The size of the stack represents the number of unmatched characters
        return stack.size();
    }
};

Java Solution for LeetCode 921

java
class Solution {
    public int minAddToMakeValid(String s) {
        // Stack to store unmatched parentheses
        // Using Deque as Stack is preferred in Java
        java.util.Deque<Character> stack = new java.util.ArrayDeque<>();
        
        for (char c : s.toCharArray()) {
            // If we see a closing bracket, check if we can match it
            if (c == ')' && !stack.isEmpty() && stack.peek() == '(') {
                stack.pop(); // Match found, remove the paired opening bracket
            } else {
                stack.push(c); // No match, add to unmatched stack
            }
        }
        
        // Remaining elements are unmatched
        return stack.size();
    }
}

Python Solution for LeetCode 921

python
class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        stack = []
        
        for char in s:
            # If current is closing and stack has a matching opening
            if char == ')' and stack and stack[-1] == '(':
                stack.pop() # Remove the matched '('
            else:
                stack.append(char) # Push unmatched char
                
        # The length of the stack is the number of moves required
        return len(stack)

Can we insert parentheses anywhere?

Yes. A common confusion is thinking we can only append or prepend. The problem allows insertion at any position. However, the stack solution implicitly handles this: an unmatched ) in the stack means we need to insert a ( before it, and an unmatched ( means we need to insert a ) after it. We don't need to calculate the indices, just the count.