Minimum Add to Make Parentheses Valid

MEDIUM

Description

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 ')'.

Approaches

Checkout 2 different approaches to solve Minimum Add to Make Parentheses Valid. Click on different approaches to view the approach and algorithm in detail.

Single Pass with a Balance Counter

A more optimized approach avoids using a stack and instead relies on a simple counter to keep track of the balance between open and close parentheses. This method achieves the same result with constant extra space.

Algorithm

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.

class Solution {
    public int minAddToMakeValid(String s) {
        int additions = 0;
        int balance = 0;

        for (char ch : s.toCharArray()) {
            if (ch == '(') {
                balance++;
            } else if (ch == ')') {
                if (balance > 0) {
                    balance--;
                } else {
                    // This ')' has no matching '('.
                    // We need to add a '(' to make it valid.
                    additions++;
                }
            }
        }

        // After the loop, 'balance' is the number of unmatched '('.
        // We need to add 'balance' number of ')' to make them valid.
        additions += balance;

        return additions;
    }
}

Complexity Analysis

Time Complexity: O(N), where N is the length of the string `s`. We iterate through the string exactly once.Space Complexity: O(1). We only use a few integer variables (`additions`, `balance`) to store our state, regardless of the input size.

Pros and Cons

Pros:

Extremely efficient in terms of space, using only a constant amount of extra memory.
Very fast due to the simple single-pass logic with no overhead from complex data structures.

Cons:

The logic might be slightly less intuitive at first glance compared to the direct simulation with a stack.

Code Solutions

Checking out 3 solutions in different languages for Minimum Add to Make Parentheses Valid. Click on different languages to view the code.

class Solution {
public
  int minAddToMakeValid(String s) {
    int ans = 0, cnt = 0;
    for (char c : s.toCharArray()) {
      if (c == '(') {
        ++cnt;
      } else if (cnt > 0) {
        --cnt;
      } else {
        ++ans;
      }
    }
    ans += cnt;
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Minimum Add to Make Parentheses Valid

Patterns:

Greedy

Data Structures:

StringStack

Companies:

Nvidia |Siemens |Walmart Labs |