Minimum Add To Make Parentheses Valid - 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. Given a parentheses string, 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 problem statement is asking us to add the minimum number of parentheses to the given string to make it valid. A valid string is one that has equal numbers of opening and closing parentheses, and they are positioned correctly.

To solve this problem, we can use a stack. We iterate through the given string and push each opening parenthesis onto the stack. Whenever we encounter a closing parenthesis, we pop the top element from the stack. If the popped element is not an opening parenthesis, we need to add a closing parenthesis, as we have encountered a closing parenthesis without a corresponding opening parenthesis. This way, we can find the minimum number of parentheses we need to add to make the string valid.

Algorithm Steps:

Create an empty stack to store the opening parentheses. Iterate through the string S. If the current character is an opening parenthesis, push it onto the stack. If the current character is a closing parenthesis, pop the top element from the stack. If the popped element is not an opening parenthesis, we need to add a closing parenthesis, so increment the counter by 1. If the stack is not empty at the end of the iteration, it means there are opening parentheses without corresponding closing parentheses, so Increment the counter by the size of the stack. Return the counter value.

Python Code:

class Solution: def minAddToMakeValid(self, S: str) -> int: stack = [] counter = 0

    for ch in S:
        if ch == '(':
            stack.append(ch)
        elif ch == ')':
            if stack:
                stack.pop()
            else:
                counter += 1
    
    counter += len(stack)
    
    return counter

Time Complexity:

The time complexity of this algorithm is O(N), where N is the length of the string. We traverse the string once, and the stack operations take O(1) time.

Space Complexity:

The space complexity of this algorithm is O(N), where N is the length of the string. In the worst case, all the characters of the string can be opening parentheses, and we need to store them in the stack.

1