Problem of The Day: Minimum Add to Make Parentheses Valid

Problem Statement

Intuition

The problem is asking us to add the minimum number of parentheses to make the string of parentheses valid. A valid parentheses string follows the rule that each opening parenthesis ‘(‘ has a matching closing parenthesis ‘)’.

My initial intuition is to use a stack to help track unmatched parentheses. As we iterate through the string, we can manage pairs of valid parentheses and count the remaining unbalanced ones.

Approach

1. Initialize an empty stack to track unmatched parentheses.
2. Iterate through the string character by character:
   • If the character is an opening parenthesis ‘(‘, push it onto the stack.
   • If the character is a closing parenthesis ‘)’, check if the stack has an unmatched opening parenthesis ‘(‘ at the top. If yes, pop it from the stack because we have found a valid pair.
   • If not, push the closing parenthesis onto the stack because it is unmatched.
3. At the end of the iteration, the stack will contain the unmatched parentheses, and the size of the stack will be the number of parentheses that need to be added to balance the string.
4. Return the size of the stack as the result.

Complexity

• Time complexity: The time complexity is \(O(n)\), where \(n\) is the length of the string. This is because we are iterating through the string once, and each operation on the stack (push or pop) takes constant time.

• Space complexity: The space complexity is \(O(n)\) in the worst case. If all parentheses are unmatched, we will have to store all characters in the stack.

Code

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

Editorial

Approach: Open Bracket Counter

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

• time: O(n)
• space: O(1)