• Posts

Problem 921 Minimum Add to Make Parentheses Valid

Problem Statement

Link - Problem 921

Question

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

Solution

class Solution {
public:
    int minAddToMakeValid(string s) {
        cin.tie(0);
        int open=0,close=0;
        for(auto &ch:s){
            if(ch == '(')
                open++;
            else
                open>0?open--:close++;
        }
        return open+close;
    }
};

Complexity Analysis

| Algorithm             | Time Complexity | Space Complexity |
| --------------------- | --------------- | ---------------- |
| Single-pass traversal | O(n)            | O(1)             |

Explanation

Intial Thoughts

To solve this problem, we should first consider how we balance parentheses in everyday writing, like keeping track of opening and closing brackets in a sentence. We need to find the minimum number of additions required to achieve this balance in a string. The approach should involve counting the number of unmatched opening and closing parentheses and determining the minimum operations needed to match them. This could involve iterating through the string to keep track of the balance between opening and closing parentheses. Key points to consider include how to handle consecutive opening or closing parentheses and how to efficiently calculate the minimum additions required.

Intuitive Analysis

An intuitive way to think about this problem is to imagine a stack of blocks, where opening parentheses represent adding a block to the stack and closing parentheses represent removing a block. If the stack is empty when we encounter a closing parenthesis, it means we need an opening parenthesis to balance it, so we increment our count of additions needed. Similarly, if there are blocks left in the stack at the end, it means we have unmatched opening parentheses, so we also need to increment our count of additions for these. This ‘stack’ analogy helps simplify the problem into keeping track of the balance between opening and closing parentheses and calculating the minimum additions required to achieve a balanced string.

1. Intuition

• The problem can be solved by maintaining a balance between opening and closing parentheses
• We can use a counter to keep track of the balance, incrementing for opening parentheses and decrementing for closing parentheses
• If the counter is negative, it means we have more closing parentheses than opening ones, so we need to add an opening parenthesis
• If the counter is positive at the end, it means we have more opening parentheses than closing ones, so we need to add a closing parenthesis for each one
• This approach works because it ensures that every opening parenthesis has a corresponding closing parenthesis
• The time complexity of this approach is O(n), where n is the length of the string, because we only need to iterate over the string once
• The space complexity is O(1), because we only need to use a constant amount of space to store the counter

2. Implementation

• We initialize two counters, open and close, to keep track of the number of opening and closing parentheses needed
• We iterate over the string s using a for loop, checking each character ch
• If ch is an opening parenthesis, we increment the open counter
• If ch is a closing parenthesis, we check if open is greater than 0, and if so, we decrement open, otherwise we increment close
• Finally, we return the sum of open and close, which represents the minimum number of moves needed to make the string valid
• The cin.tie(0) line is used to improve the performance of the input/output operations
• The return open+close line calculates the minimum number of moves needed to make the string valid

Complexity Analysis

Time Complexity:

• The algorithm iterates over the input string s once, resulting in a linear relationship between the input size n and the time taken to execute the algorithm.
• The dominant operation is the single-loop traversal using for(auto &ch:s), which performs a constant amount of work for each character in the string.
• Therefore, the time complexity is justified as O(n), where n is the length of the input string s, because the number of operations grows linearly with the size of the input.

Space Complexity:

• The algorithm uses a constant amount of space to store the variables open and close, regardless of the size of the input string s.
• The data structure impact is minimal, with no additional data structures such as arrays or trees used that would depend on the input size.
• Hence, the space complexity is justified as O(1), indicating that the algorithm’s memory usage does not grow with the size of the input.

Footnote

This question is rated as Medium difficulty.

Similar Questions: