Problem Description

The Minimum Add to Make Parentheses Valid problem asks you to determine the minimum number of parentheses that must be added to a given string s (consisting only of the characters '(' and ')') so that the resulting string is a valid parentheses expression.

A string of parentheses is considered valid if:

• Every opening parenthesis '(' has a corresponding closing parenthesis ')'.
• Parentheses are closed in the correct order (no closing before opening).

Constraints:

• The input string s consists only of '(' and ')'.
• There is only one valid answer for each input.
• You do not need to modify the original string, only return the minimum number of insertions needed.

Thought Process

At first glance, the problem seems to ask for balancing parentheses by counting mismatches. A brute-force approach might be to try every possible insertion, but this is inefficient. Instead, we should look for a way to efficiently scan the string and keep track of the balance between opening and closing parentheses.

The key insight is to process the string from left to right, maintaining a counter for the current "open" parentheses that need matching. Every time we see a '(', we increment this counter; every time we see a ')', we decrement it if there's a matching open, or count it as an unmatched close if not. At the end, any leftover opens or unmatched closes must be fixed by insertions.

This way, we avoid unnecessary insertions and only add what's strictly needed, making the solution optimal.

Solution Approach

Let's break down the algorithm step by step:

1. Initialize Counters:
   • open_needed: Counts the number of unmatched opening parentheses '(' that need a closing parenthesis.
   • insertions: Counts the number of insertions needed for unmatched closing parentheses ')'.
2. Iterate Through the String:
   • For each character in s:
   • If it's '(', increment open_needed.
   • If it's ')':
     • If open_needed is greater than zero, decrement open_needed (match a pending open).
     • Otherwise, increment insertions (need to add an open before this close).
3. Final Calculation:
   • The total insertions needed is insertions + open_needed.
   • insertions: unmatched closing parentheses.
   • open_needed: unmatched opening parentheses that need closing.

This algorithm is efficient because it only requires a single pass through the string and constant extra space.

Example Walkthrough

Let's walk through the input s = "())(" step by step:

• Initialize: open_needed = 0, insertions = 0
• First character: '('
  • Increment open_needed to 1 (need a close for this open)
• Second character: ')'
  • open_needed > 0, so decrement open_needed to 0 (pair matched)
• Third character: ')'
  • open_needed == 0, so increment insertions to 1 (need to add an open before this close)
• Fourth character: '('
  • Increment open_needed to 1 (need a close for this open)
• End of string: open_needed = 1, insertions = 1
• Result: insertions + open_needed = 2

We need to add 1 closing parenthesis for the last open, and 1 opening parenthesis for the unmatched close.

Time and Space Complexity

Brute-Force Approach: Trying every possible insertion would be exponential in time and space, as the number of possible combinations grows rapidly with string length.

Optimized Approach (described above):

• Time Complexity: O(n), where n is the length of the string. We scan the string once.
• Space Complexity: O(1), as we only use a couple of integer counters regardless of input size.

Summary

The problem is solved by tracking unmatched opening and closing parentheses in a single pass over the string. By incrementing and decrementing counters as we encounter '(' and ')', we can efficiently determine the minimum number of insertions needed to make the string valid. This approach is optimal, both in time and space, and elegantly sidesteps the need for complex stack manipulation or brute-force exploration.

Code Implementation

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        open_needed = 0
        insertions = 0
        for c in s:
            if c == '(':
                open_needed += 1
            else:  # c == ')'
                if open_needed > 0:
                    open_needed -= 1
                else:
                    insertions += 1
        return insertions + open_needed
      

class Solution {
public:
    int minAddToMakeValid(string s) {
        int open_needed = 0, insertions = 0;
        for (char c : s) {
            if (c == '(') {
                open_needed++;
            } else { // c == ')'
                if (open_needed > 0) {
                    open_needed--;
                } else {
                    insertions++;
                }
            }
        }
        return insertions + open_needed;
    }
};
      

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

var minAddToMakeValid = function(s) {
    let openNeeded = 0, insertions = 0;
    for (let c of s) {
        if (c === '(') {
            openNeeded++;
        } else { // c === ')'
            if (openNeeded > 0) {
                openNeeded--;
            } else {
                insertions++;
            }
        }
    }
    return insertions + openNeeded;
};