Minimum Add to Make Parentheses Valid

class Solution {
public:
    int minimumInsertionsToBalance(string str) {
        int open = 0;
        int requiredInserts = 0;
        for (char ch : str) {
            if (ch == '(') {
                open++;
            } else {
                // Close one if an opening bracket was seen
                open > 0 ? open-- : requiredInserts++;
            }
        }
        // Add the extra required closing brackets to balance remaining open ones
        return requiredInserts + open;
    }
};

This C++ solution focuses on determining the minimum number of insertions required to make a string of parentheses valid. The approach utilizes a counter mechanism to track unbalanced parentheses as the string is processed character by character.

• Initialize two counters:

  • open to keep track of unmatched opening brackets.
  • requiredInserts to count the insertions needed for balancing closing brackets.

• Iterate through each character in the string:

  • Increment the open counter for every '(' encountered.
  • For each ')', check if there's an unmatched '(' available:
    • If yes, decrement the open counter.
    • If no opening bracket is available, increment the requiredInserts counter by one.

• After completing the iteration through the string, add any remaining unmatched opening brackets to the requiredInserts. This sum represents the total insertions needed to balance the parentheses.

The function finally returns the total number of insertions (requiredInserts + open) required to make the entire string of parentheses valid. This method effectively accounts for both excess opening and closing brackets, ensuring the string achieves proper balance with minimal modifications.

class Solution {

    public int addMinParentheses(String s) {
        int openCount = 0;
        int closeNeeded = 0;

        for (char ch : s.toCharArray()) {
            if (ch == '(') {
                openCount++;
            } else {
                if (openCount > 0) {
                    openCount--;
                } else {
                    closeNeeded++;
                }
            }
        }

        return closeNeeded + openCount;
    }
}

This Java solution addresses the problem of determining the minimum number of additional parentheses required to make an input string of parentheses balanced. The solution utilizes two counters: openCount for tracking unbalanced opening parentheses '(' and closeNeeded for tracking the necessary closing parentheses ')' to balance the string.

• The method addMinParentheses(String s) iterates through each character in the string.
• If the character is '(', increment openCount.
• If the character is ')':
  • If openCount is greater than zero, decrement openCount (successfully balancing one opening with a closing bracket).
  • If openCount is zero, increment closeNeeded (a closing bracket without a matching opening bracket).

The method returns the sum of closeNeeded and openCount. The total represents the minimum insertions needed where openCount shows the number of unmatched '(' and closeNeeded shows the unmatched ')'. This approach ensures that all opening and closing brackets can form pairs by the end of the string analysis.

class Solution:
    def minimumInsertionsToBalance(self, parentheses: str) -> int:
        open_count = 0
        additions_needed = 0

        for char in parentheses:
            if char == "(":
                open_count += 1
            elif open_count > 0:
                open_count -= 1
            else:
                additions_needed += 1

        return additions_needed + open_count

The Python solution provided tackles the problem of making an unbalanced string of parentheses valid through the minimum number of insertions. The function minimumInsertionsToBalance accepts a string of parentheses and determines how many additions are necessary to balance it.

The solution works as follows:

1. Initialize two counters: open_count to track the number of unmatched opening parentheses and additions_needed for the count of insertions required.

2. Iterate through each character in the input string.

   • If the character is an opening parenthesis "(", increment open_count.
   • If it's a closing parenthesis ")", check if there’s an unmatched opening parenthesis. If so, decrement open_count. Otherwise, increase additions_needed since an unmatched closing parenthesis needs a corresponding opening one.

3. After processing all characters, add any remaining unmatched opening parentheses (open_count) to additions_needed. This accounts for each unmatched opening parenthesis needing a matching closing parenthesis.

The result, additions_needed + open_count, is the total number of insertions needed to balance the parentheses fully. This approach efficiently ensures each parenthesis is properly paired by directly counting mismatches and addressing them, achieving the balance with the minimum additions.