Problem Description

You are given a string s that contains only parentheses characters '(' and ')'. A valid parentheses string must follow these rules:

• It can be an empty string
• It can be formed by concatenating two valid strings (like AB where both A and B are valid)
• It can be formed by wrapping a valid string with parentheses (like (A) where A is valid)

In simpler terms, every opening parenthesis '(' must have a matching closing parenthesis ')' that comes after it, and they must be properly nested.

Your task is to find the minimum number of parentheses (either '(' or ')') that you need to insert at any position in the string to make it valid.

For example:

• If s = "()))", you need to add 2 parentheses. You could add '(' at the beginning and another '(' after the first character to get "(()())"
• If s = "(((", you need to add 3 closing parentheses ')' to balance the opening ones

The solution uses a stack-based approach where:

• When encountering '(', it gets pushed to the stack
• When encountering ')', if there's a matching '(' on top of the stack, they cancel out (pop the stack); otherwise, the ')' is unmatched and gets pushed to the stack
• After processing all characters, the stack contains all unmatched parentheses, and its size equals the minimum additions needed

Intuition

The key insight is that we need to track unmatched parentheses. When we see a valid pair (an opening '(' followed eventually by a closing ')'), these two cancel each other out and don't require any additions.

Think of it like balancing a scale:

• Every '(' adds weight to the left side
• Every ')' adds weight to the right side
• When we can match a ')' with a previous '(', they balance out

The challenge is that order matters - a ')' can only match with a '(' that comes before it. This naturally leads us to use a stack:

1. When we see '(', we're creating a "debt" that needs to be paid with a future ')'
2. When we see ')', we check if there's an unpaid debt (an unmatched '(' in our stack)
   • If yes, they match! We remove the debt (pop from stack)
   • If no, this ')' itself becomes unmatched and needs a '(' added somewhere before it

After processing the entire string, whatever remains in our stack represents:

• Unmatched '(' characters that need ')' additions
• Unmatched ')' characters that need '(' additions

The beauty of this approach is that we don't need to actually decide where to insert the parentheses - we just count how many are unmatched. Each unmatched parenthesis requires exactly one addition to balance it out, so the stack size at the end gives us our answer directly.

Learn more about Stack and Greedy patterns.

Solution Approach

The solution implements a greedy stack-based approach to count unmatched parentheses.

Algorithm Steps:

1. Initialize an empty stack - This will store all unmatched parentheses as we process the string.

2. Iterate through each character c in the string s:

   • If c is a closing parenthesis ')':
     • Check if the stack is not empty AND the top element is an opening parenthesis '('
     • If both conditions are true, we have found a matching pair:
       • Pop the '(' from the stack (successful match)
     • Otherwise, this ')' is unmatched:
       • Push ')' onto the stack
   • If c is an opening parenthesis '(':
     • Always push it onto the stack (it's waiting for a future match)

3. Return the stack size - After processing all characters, the stack contains only unmatched parentheses. Each unmatched parenthesis requires exactly one addition to balance it.

Why This Works:

The greedy nature of the algorithm ensures we match parentheses as soon as possible. When we see a ')', we immediately try to match it with the most recent unmatched '('. This is optimal because:

• Matching early prevents accumulation of unmatched parentheses
• Each match reduces the number of additions needed by 2 (one '(' and one ')' that would otherwise need partners)

Time Complexity: O(n) where n is the length of the string - we process each character once.

Space Complexity: O(n) in the worst case when all parentheses are unmatched (e.g., all '(' or all ')').

Example Walkthrough

Let's walk through the example s = "())(" step by step to illustrate how the solution works.

Initial State:

• String: "())("
• Stack: [] (empty)
• Position: 0

Step 1: Process '(' at index 0

• Character is '(', so push it to stack
• Stack: ['(']

Step 2: Process ')' at index 1

• Character is ')'
• Check: Is stack non-empty AND top element is '('? Yes!
• We found a match! Pop '(' from stack
• Stack: [] (empty again)

Step 3: Process ')' at index 2

• Character is ')'
• Check: Is stack non-empty AND top element is '('? No (stack is empty)
• This ')' is unmatched, push it to stack
• Stack: [')']

Step 4: Process '(' at index 3

• Character is '(', so push it to stack
• Stack: [')', '(']

Final Result:

• Stack contains: [')', '(']
• Stack size = 2
• Answer: 2 (we need to add 2 parentheses to make the string valid)

To verify: The unmatched ')' at position 2 needs a '(' before it, and the unmatched '(' at position 3 needs a ')' after it. We could transform the string to "(())())" by adding '(' at the beginning and ')' at the end, making it valid with exactly 2 additions.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. This is because the algorithm iterates through each character in the string exactly once, performing constant-time operations (checking conditions, pushing to stack, or popping from stack) for each character.

The space complexity is O(n), where n is the length of the string s. In the worst-case scenario, all characters in the string are unmatched (for example, a string of all '(' or all ')'), which means all characters would be pushed onto the stack, requiring O(n) additional space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrectly Counting Matches Instead of Unmatched Parentheses

A common mistake is trying to count successful matches and then calculating unmatched parentheses indirectly. This often leads to complex logic and off-by-one errors.

Incorrect Approach:

def minAddToMakeValid(self, s: str) -> int:
    matches = 0
    open_count = 0
    close_count = 0
  
    for char in s:
        if char == '(':
            open_count += 1
        else:
            if open_count > 0:
                matches += 1
                open_count -= 1
            else:
                close_count += 1
  
    # Bug: This doesn't correctly handle all cases
    return len(s) - matches * 2  # Wrong!

Why it fails: This approach tries to count matches and derive unmatched count, but the calculation becomes error-prone and doesn't properly track remaining unmatched opening parentheses.

Correct Fix: Directly track unmatched parentheses using the stack approach shown in the solution.

Pitfall 2: Using Counter Variables Instead of Stack

Some might try to optimize by using two counters instead of a stack, but implement it incorrectly:

Incorrect Implementation:

def minAddToMakeValid(self, s: str) -> int:
    open_needed = 0
    close_needed = 0
  
    for char in s:
        if char == '(':
            open_needed += 1  # Wrong: should be close_needed
        else:
            if open_needed > 0:  # Wrong: should check close_needed
                open_needed -= 1
            else:
                close_needed += 1
  
    return open_needed + close_needed

Correct Counter-Based Solution:

def minAddToMakeValid(self, s: str) -> int:
    open_unmatched = 0  # Count of unmatched '('
    close_unmatched = 0  # Count of unmatched ')'
  
    for char in s:
        if char == '(':
            open_unmatched += 1
        else:  # char == ')'
            if open_unmatched > 0:
                open_unmatched -= 1  # Found a match
            else:
                close_unmatched += 1  # No '(' to match with
  
    return open_unmatched + close_unmatched

Pitfall 3: Misunderstanding Stack Behavior

Some developers might think they need to check the entire stack or implement complex matching logic:

Overcomplicated Approach:

def minAddToMakeValid(self, s: str) -> int:
    stack = []
  
    for char in s:
        if char == ')':
            # Unnecessary: searching through entire stack
            found = False
            temp = []
            while stack:
                top = stack.pop()
                if top == '(' and not found:
                    found = True
                else:
                    temp.append(top)
            if not found:
                temp.append(')')
            stack.extend(reversed(temp))
        else:
            stack.append(char)
  
    return len(stack)

Why it's wrong: The greedy approach only needs to check the immediate top of the stack. Looking deeper violates the proper nesting requirement and overcomplicates the solution.

Key Takeaway

The elegance of the stack solution lies in its simplicity: only check the top element when encountering a ')'. If it's '(', they match and both are removed. Otherwise, the ')' is unmatched and gets added to the stack. This greedy matching ensures optimal results while maintaining clean, understandable code.