Minimum Add to Make Parentheses Valid

A parentheses string is valid if and only if:

• It is the empty string,
• It can be written as AB (A concatenated with B), where A and B are valid strings, or
• It can be written as (A), where A is a valid string.

You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.

• For example, if s = "()))", you can insert an opening parenthesis to be "(****(****)))" or a closing parenthesis to be "())****)****)". (* indicates insertion)

Return the minimum number of moves required to make s valid.

For example:

• Input: s = "()))", Output: 1
• Input: s = "(((", Output: 3

Question: Minimum Add to Make Parentheses Valid

You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string. Return the minimum number of moves required to make s valid.

For example:

• s = "())" should return 1
• s = "(((" should return 3

Solution

Here's a Java solution to find the minimum number of moves required to make a parentheses string valid:

class Solution {
    /**
     * Given a string S of '(' and ')' parentheses, we add the minimum number of parentheses ('(' or ')',
     * and in any positions) so that the resulting parentheses string is valid.
     *
     * Formally, a parentheses string is valid if and only if:
     *
     * It is the empty string, or
     * It can be written as AB (A concatenated with B), where A and B are valid strings, or
     * It can be written as (A), where A is a valid string.
     *
     * Example 1:
     *
     * Input: "())"
     * Output: 1
     *
     * Example 2:
     *
     * Input: "((("
     * Output: 3
     *
     * Example 3:
     *
     * Input: "()"
     * Output: 0
     *
     * Example 4:
     *
     * Input: "()))(("
     * Output: 4
     *
     * Note:
     *
     * S.length <= 1000
     * S only consists of '(' and ')' characters.
     */
    public int minAddToMakeValid(String S) {
        int ans = 0;
        int bal = 0;
        for (int i = 0; i < S.length(); ++i) {
            if (S.charAt(i) == '(') {
                bal++;
            } else {
                bal--;
            }
            // If balance < 0, add to balance and increment answer
            if (bal == -1) {
                ans++;
                bal++;
            }
        }
        return ans + bal;
    }
}

Explanation

1. Initialization: ans stores the number of moves needed, and bal tracks the balance of open parentheses.
2. Iterating through the String: We loop through each character of the input string S.
3. Open Parenthesis: If the character is an open parenthesis (, we increment bal.
4. Close Parenthesis: If the character is a close parenthesis ), we decrement bal.
5. Balance Check: If bal becomes negative, it means we have more close parentheses than open ones. In this case, we need to add an open parenthesis to balance it. So, we increment ans and also increment bal to reset the balance.
6. Final Result: After the loop, if bal is still positive, it means we have more open parentheses than close ones. So, we add the remaining bal to ans.
7. Return: Finally, we return the total number of moves needed.

Big(O) Run-time Analysis

The time complexity is O(N), where N is the length of the input string S, because we iterate through each character once.

Big(O) Space Usage Analysis

The space complexity is O(1) because we only use a constant amount of extra space to store the ans and bal variables.