921. Minimum Add to Make Parentheses Valid

Problem Description

The problem presents a situation where we have a string s which consists only of the parentheses characters "(" and ")". A valid parentheses string is defined as such if it meets one of the following criteria:

It's an empty string.
It can be separated into two substrings A and B such that both A and B are themselves valid parentheses strings.
It can be enclosed within a pair of parentheses — meaning if A is a valid string, then (A) is also valid.

The task at hand is to determine the fewest number of moves required to make the initial string s into a valid parentheses string. Each move consists of inserting exactly one parenthesis character (either "(" or ")") at any position within the string.

Intuition

The intuition behind the solution stems from the understanding of how a valid parentheses string is structured. Fundamentally, for every opening parenthesis "(", there should be a corresponding closing parenthesis ")" to make it valid. If we traverse the string from left to right, at any point, the number of closing parentheses should not exceed the number of opening parentheses.

When encountering an opening parenthesis, it suggests the start of a potentially valid substring, so we increment a counter. Upon finding a closing parenthesis, if there is a previously unmatched opening parenthesis (our counter is greater than zero), we can pair this closing parenthesis with that opening parenthesis, decrementing the counter. If the counter is zero (indicating no unmatched opening parentheses), we require an additional opening parenthesis to match the current closing parenthesis, thus incrementing the answer—keeping track of moves needed.

Finally, after running through the string, if there's any unmatched opening parenthesis remaining (counter is not zero), those need matching closing parentheses. So, we add the number of remaining unmatched opening parentheses to the answer.

By accumulating the moves required to insert missing opening or closing parentheses, we can calculate the minimum number of moves to make the string valid.

Learn more about Stack and Greedy patterns.

Solution Approach

The algorithm implemented in the solution is relatively straightforward and efficient, using a single pass through the string, and it relies on the use of counters to track the state of the parentheses. No additional data structures are needed, which makes the space complexity constant, O(1), as we only use a couple of integer variables to keep track of counts. The algorithm can be described as follows:

Initialize two variables, ans and cnt to zero. Here, ans will hold the total number of moves required to make the string valid, and cnt will keep track of the balance of opening and closing parentheses as we iterate through the string.
Iterate through each character c of the given string s:
- If c is an opening parenthesis "(", increment the cnt counter, since we have an additional unmatched opening parenthesis.
- If c is a closing parenthesis ")":
  - If cnt is greater than zero, it means there is a preceding unmatched opening parenthesis which can be paired with this closing parenthesis, so we decrement cnt.
  - If cnt is zero, it means there are no unmatched opening parentheses to pair with this closing parenthesis, therefore, we need to add an opening parenthesis, thus we increment the ans counter.
After the iteration is complete, if there is a non-zero cnt, this means there are cnt number of unmatched opening parentheses remaining. These will all need matching closing parentheses, so we add cnt to ans.
The final value of ans is the minimum number of moves required to make the string valid.

This approach works well as it leverages the inherent structure of valid parentheses strings. Since we only look at the balance between opening and closing brackets without necessarily considering their exact positions, the order in which we would insert the additional parentheses doesn't change the number of moves we need to make, making this approach both simple and effective. The time complexity of the solution is linear, O(n), where n is the length of the input string because we go through the string exactly once.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example here with the string s = ")))(((" to illustrate the solution approach.

We initialize two variables, ans = 0 and cnt = 0.
We start iterating through the string s from left to right.
- We begin with the first character ):
  - cnt is at 0, meaning there are no unmatched opening ( for this ). We would need one opening ( before this one to balance it out, so we increment ans to 1. Now, ans = 1 and cnt remains 0.
- The second character is ): the same logic applies, so ans is incremented again. Now, ans = 2, and cnt is still 0.
- For the third character ), we repeat the same increment on ans. So, ans = 3, and cnt = 0.
- We now encounter an opening parenthesis (. We increment cnt by 1 because we have one unmatched opening parenthesis, so cnt = 1.
- The fifth character is another (, so now cnt = 2.
- The sixth character is yet again (, bringing cnt to 3.
We have finished iterating through the string. Now we must account for the unmatched opening parentheses. We have cnt = 3 unmatched ( left, which means we need 3 matching closing ) to make the string valid.
We add cnt to ans. So, ans becomes 3 + 3 = 6.

The minimum number of moves required to make the string )))((( valid by insertions is ans = 6. We can achieve this by inserting three opening ( at the beginning and three closing ) at the end, resulting in a valid parentheses string ((())).

Solution Implementation

1class Solution:
2    def minAddToMakeValid(self, s: str) -> int:
3        # Initialize variables to count the necessary additions and 
4        # keep track of the unmatched parentheses.
5        additions_needed = unmatched_open = 0
6      
7        # Iterate through each character in the string.
8        for char in s:
9            # If the character is an open parenthesis, increment the unmatched count.
10            if char == '(':
11                unmatched_open += 1
12            # If it's a close parenthesis and there's an unmatched open, pair it and decrement.
13            elif unmatched_open:
14                unmatched_open -= 1
15            # Otherwise, if there is no unmatched open, we need an addition (an open parenthesis).
16            else:
17                additions_needed += 1
18      
19        # Add any remaining unmatched open parentheses to the total additions needed.
20        additions_needed += unmatched_open
21      
22        # Return the total number of additions needed to make the string valid.
23        return additions_needed
24

1class Solution {
2    public int minAddToMakeValid(String s) {
3        int additionsRequired = 0; // Count of parentheses to add to make the string valid
4        int balanceCount = 0;      // Keep track of the balance between opening and closing brackets
5      
6        // Loop through each character in the string
7        for (char character : s.toCharArray()) {
8            if (character == '(') {
9                // An opening parenthesis increments the balance count
10                balanceCount++;
11            } else if (balanceCount > 0) {
12                // A closing parenthesis decrements the balance count if there are unmatched opening ones
13                balanceCount--;
14            } else {
15                // If there are no unmatched opening, we need an opening parenthesis
16                additionsRequired++;
17            }
18        }
19      
20        // Add the remaining unmatched opening parentheses to the count of required additions
21        additionsRequired += balanceCount;
22      
23        // Return the total number of additions required to make the string valid
24        return additionsRequired;
25    }
26}
27

1class Solution {
2public:
3    int minAddToMakeValid(string s) {
4        int balance = 0; // This will keep track of the balance between '(' and ')'
5        int additions = 0; // Counter for the required additions to make the string valid
6
7        // Loop through each character in the string
8        for (char c : s) {
9            // If it's an opening bracket, increase the balance
10            if (c == '(') {
11                balance++;
12            }
13            // If it's a closing bracket, check if there is a matching opening bracket
14            else {
15                // If there is a matching opening bracket, decrement the balance
16                if (balance > 0) {
17                    balance--;
18                }
19                // If there is no matching opening bracket, increment additions
20                else {
21                    additions++;
22                }
23            }
24        }
25
26        // Add outstanding balance to the additions. These are unmatched opening brackets.
27        additions += balance;
28
29        // Return the total number of additions required to make the string valid
30        return additions;
31    }
32};
33

1// Function to calculate the minimum number of additions needed to make the parentheses string valid
2function minAddToMakeValid(s: string): number {
3    let balance = 0; // This will keep track of the balance between '(' and ')'
4    let additions = 0; // Counter for the additions required to make the string valid
5
6    // Loop through each character in the string
7    for (let i = 0; i < s.length; i++) {
8        const c = s[i];
9
10        // If it's an opening bracket, increase the balance
11        if (c === '(') {
12            balance++;
13        } else { // Implicitly c is ')', as it's not '('
14            // If there is a matching opening bracket, decrement the balance
15            if (balance > 0) {
16                balance--;
17            } else {
18                // If there is no matching opening bracket, increment additions
19                additions++;
20            }
21        }
22    }
23
24    // Add any unmatched opening brackets to the additions
25    additions += balance;
26
27    // Return the total number of additions required to make the string valid
28    return additions;
29}
30

Time and Space Complexity

Time Complexity

The time complexity of the provided code is O(n), where n is the length of the input string s. This is because the code iterates through each character of the string exactly once, executing a constant number of operations for each character.

Space Complexity

The space complexity of the provided code is O(1), which signifies constant space. This is due to the fact that the space required does not scale with the size of the input string. The variables ans and cnt require a fixed amount of space regardless of the length of s.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the following shows the order of node visit in a Breadth-first Search?

I don’t know