Minimum Additions To Make Valid String - Leetcode Solution

Problem Statement:

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.

You need to return the minimum number of parentheses we must add to make the resulting string valid.

Example 1:

Input: "())" Output: 1

Example 2:

Input: "(((" Output: 3

Example 3:

Input: "()" Output: 0

Example 4:

Input: "()))((" Output: 4

Solution:

The idea behind the solution of this problem is to use a stack data structure. We can traverse the string character by character and use a stack to keep track of the opening parentheses.

If the current character is an opening parenthesis, i.e., '(', we push it to the stack. If the character is a closing parenthesis, i.e., ')', we check if the top of the stack is an opening parenthesis, i.e., '('. If the top of the stack is not an opening parenthesis, we add a closing parenthesis to the string and push it to the stack. If the top of the stack is an opening parenthesis, we pop it from the stack.

After traversing the entire string, the stack will contain all the opening parentheses that were not matched with closing parentheses. We can calculate the number of minimum additions required by returning the size of the stack.

Let's look at the dry run of the above approach using an example:

Example: S = "()))(("

Initially, the stack is empty.

For the first character '(', we push it onto the stack.

For the second character ')', we check the top of the stack which is '('. Since it is an opening parenthesis, we pop it from the stack.

For the third character ')', we check the top of the stack which is empty. We add a closing parenthesis to the string and push it onto the stack.

After the third character, the stack contains a single opening parenthesis.

For the fourth character '(', we push it onto the stack.

For the fifth character ')', we check the top of the stack which is '('. Since it is an opening parenthesis, we pop it from the stack.

For the sixth character ')', we check the top of the stack which is empty. We add a closing parenthesis to the string and push it onto the stack.

After traversing the entire string, the stack contains two opening parentheses. The minimum number of additions required is 2.

Algorithm:

• Initialize a stack to store the opening parentheses.
• Initialize a counter to count the minimum additions required.
• Traverse the string character by character.
• If the current character is an opening parenthesis, i.e., '(', push it onto the stack.
• If the current character is a closing parenthesis, i.e., ')', check if the top of the stack is an opening parenthesis, i.e., '('. If the top of the stack is not an opening parenthesis, add a closing parenthesis to the string and push it onto the stack. If the top of the stack is an opening parenthesis, pop it from the stack.
• After traversing the entire string, the stack contains all the opening parentheses that were not matched with closing parentheses. Return the size of the stack which is the minimum number of additions required.

Time Complexity: O(n) where n is the length of the string.

Space Complexity: O(n) for the stack.

Here is the Python code for the above approach:

class Solution: def minAddToMakeValid(self, S: str) -> int: stack = [] count = 0 for c in S: if c == '(': stack.append(c) else: if not stack or stack[-1] != '(': count += 1 stack.append(')') else: stack.pop() count += len(stack) return count

1