921. 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 "())))".

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

Example 1:

Input: s = "())"
Output: 1

Example 2:

Input: s = "((("
Output: 3

Constraints:

• 1 <= s.length <= 1000
• s[i] is either '(' or ')'.

Approach 01:

class Solution {
public:
    int minAddToMakeValid(string parenthesesString) {
        int leftUnmatched = 0;
        int rightUnmatched = 0;

        for (const char currentChar : parenthesesString) {
            if (currentChar == '(') {
                ++leftUnmatched;
            } else {
                if (leftUnmatched == 0)
                    ++rightUnmatched;
                else
                    --leftUnmatched;
            }
        }

        return leftUnmatched + rightUnmatched;
    }
};

class Solution:
    def minAddToMakeValid(self, parenthesesString):
        leftUnmatched = 0
        rightUnmatched = 0

        for currentChar in parenthesesString:
            if currentChar == '(':
                leftUnmatched += 1
            else:
                if leftUnmatched == 0:
                    rightUnmatched += 1
                else:
                    leftUnmatched -= 1

        return leftUnmatched + rightUnmatched

Time Complexity

• Iterating through the string:

  The function iterates through each character in the input string exactly once to count the unmatched left and right parentheses. This takes \(O(n)\), where \(n\) is the length of the input string.

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where \(n\) is the length of the input string.

Space Complexity

• Auxiliary Space:

  The function only uses a constant amount of extra space to store the two variables leftUnmatched and rightUnmatched. Therefore, the space complexity is \(O(1)\).

• Overall Space Complexity:

  The overall space complexity is \(O(1)\), as the amount of extra space used does not depend on the size of the input string.