Problem of The Day: Minimum Add to Make Parentheses Valid

Problem Statement

Intuition

The problem asks us to balance parentheses. Each valid pair of parentheses () must be accounted for, so the idea is to use a stack to keep track of unmatched parentheses as we traverse the string.

Approach

We can use a stack to help with balancing the parentheses. As we iterate through the string:

1. Push any opening parenthesis ( onto the stack.
2. If we encounter a closing parenthesis ), check the stack:
   • If the stack is not empty and the top of the stack is an opening parenthesis (, we have found a valid pair, so we pop it from the stack.
   • Otherwise, we push the closing parenthesis ) onto the stack.

At the end of the traversal, the stack will contain only the unbalanced parentheses, and its size will tell us the number of insertions needed to balance the string.

Complexity

• Time complexity:

  The time complexity is \(O(n)\), where \(n\) is the length of the input string s. We process each character once.

• Space complexity: The space complexity is \(O(n)\) in the worst case, where all characters are unbalanced, meaning they are all stored in the stack.

Code

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        stack = []
        for c in s:
            if not stack:
                stack.append(c)
            else:
                if stack[-1] == '(' and c == ')':
                    stack.pop()
                else:
                    stack.append(c)
        return len(stack)

Editorial

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        open_brackets = 0
        min_adds_required = 0

        for c in s:
            if c == "(":
                open_brackets += 1
            else:
                if open_brackets > 0:
                    open_brackets -= 1
                else:
                    min_adds_required += 1

        # Add the remaining open brackets as closing brackets would be required.
        return min_adds_required + open_brackets