Minimum Add to Make Parentheses Valid

• Initialize two counters: additions = 0 and balance = 0.
• Iterate through each character of the input string s.
• If the character is (, it increases the number of unmatched open parentheses, so we increment balance.
• If the character is ):
  • If balance > 0, it means there's an unmatched ( available to be paired. We decrement balance.
  • If balance == 0, this ) has no preceding (. It's an invalid parenthesis. We need to add one ( to fix it. So, we increment additions.
• After iterating through the entire string, if balance is still positive, it represents the number of unmatched ( at the end of the string. Each of these requires a ) to be added.
• The total minimum additions is the sum of additions (for invalid )) and the final balance (for unmatched ().

Instead of using a stack, we can solve this problem by iterating through the string just once while keeping track of the 'balance' of the string. The balance counter represents the number of open parentheses that are waiting for a closing one.

• We initialize balance and additions to zero.
• When we encounter an opening parenthesis (, we increment balance because we now have one more open parenthesis that needs a match.
• When we encounter a closing parenthesis ), we check the balance.
  • If balance is greater than 0, it means there's an open parenthesis waiting. We can use this ) to form a pair, so we decrement balance.
  • If balance is 0, it means there are no open parentheses waiting for a match. This ) is therefore invalid. To make it valid, we must insert an opening parenthesis. We count this by incrementing additions.

After the loop, the balance counter holds the number of opening parentheses that were never closed. To make the string valid, we need to add a closing parenthesis for each of these. So, the total number of additions is the additions we've counted so far, plus the final value of balance.

For example, with s = "()))((:

• (: balance becomes 1.
• ): balance becomes 0.
• ): balance is 0, so additions becomes 1.
• (: balance becomes 1.
• (: balance becomes 2.
• End of loop. Total additions = additions + balance = 1 + 2 = 3.

1class Solution {2    public int minAddToMakeValid(String s) {3        int additions = 0;4        int balance = 0;5 6        for (char ch : s.toCharArray()) {7            if (ch == '(') {8                balance++;9            } else if (ch == ')') {10                if (balance > 0) {11                    balance--;12                } else {13                    // This ')' has no matching '('.14                    // We need to add a '(' to make it valid.15                    additions++;16                }17            }18        }19 20        // After the loop, 'balance' is the number of unmatched '('.21        // We need to add 'balance' number of ')' to make them valid.22        additions += balance;23 24        return additions;25    }26}

• Initialize an empty stack to store opening parentheses.
• Initialize a counter additions to 0.
• Iterate through each character of the input string s.
• If the character is an opening parenthesis (, push it onto the stack.
• If the character is a closing parenthesis ):
  • Check if the stack is empty. If it is, this ) has no matching (. We must add an opening parenthesis to make it valid. Increment additions.
  • If the stack is not empty, it means there's a waiting (. We pop from the stack, signifying a successful match.
• After the loop finishes, any remaining parentheses in the stack are unmatched opening ones. Each of them requires a closing parenthesis to be added.
• The total minimum additions will be the current value of additions plus the final number of elements left in the stack.

We can simulate the process of matching parentheses using a stack. The core idea is that an opening parenthesis ( is 'waiting' for a closing one ). The stack is a perfect tool to manage these 'waiting' parentheses.

For each character in the string:

• If we see an opening parenthesis (, we push it onto the stack. It will wait there until a matching ) is found.
• If we see a closing parenthesis ), we check the stack. If the stack is not empty, we can pop an opening parenthesis, forming a valid pair (). If the stack is empty, it means this closing parenthesis has no preceding opening parenthesis to match with. This is an invalid state. To fix it, we must add an opening parenthesis. We count this as one required addition.

After iterating through the entire string, the stack may still contain some opening parentheses. These are the ones that never found a matching closing parenthesis. To make the string valid, each of these requires a closing parenthesis to be added. Therefore, the final number of additions is the count of additions for invalid ) plus the number of ( left in the stack.

1import java.util.Stack;2 3class Solution {4    public int minAddToMakeValid(String s) {5        Stack<Character> stack = new Stack<>();6        int additions = 0;7 8        for (char ch : s.toCharArray()) {9            if (ch == '(') {10                stack.push(ch);11            } else if (ch == ')') {12                if (stack.isEmpty()) {13                    // This ')' is unmatched, needs a '(' before it.14                    additions++;15                } else {16                    // Found a pair, pop the matching '('.17                    stack.pop();18                }19            }20        }21 22        // Any remaining '(' in the stack are unmatched.23        // They need a corresponding ')' to be added.24        additions += stack.size();25 26        return additions;27    }28}