LeetCode 921: Minimum Add to Make Parentheses Valid

Problem Restatement

We are given a string s containing only parentheses:

"("
")"

In one move, we may insert one parenthesis at any position.

Return the minimum number of insertions needed to make the string valid.

A valid parentheses string is one where every opening parenthesis has a matching closing parenthesis in the correct order. The official statement defines the operation as inserting one parenthesis anywhere in the string.

Input and Output

Function shape:

def minAddToMakeValid(s: str) -> int:
    ...

Examples

Example 1:

s = "())"

The first two characters form a valid pair:

()

The final ")" has no matching "(".

We need to insert one "(".

Answer:

1

Example 2:

s = "((("

There are three unmatched opening parentheses.

We need three closing parentheses:

")))"

Answer:

3

Example 3:

s = "()))(("

Process it mentally:

()     matched
))     two unmatched closing parentheses
((     two unmatched opening parentheses

We need:

2 opening parentheses + 2 closing parentheses = 4

Answer:

4

First Thought: Use a Stack

A direct way is to simulate matching parentheses with a stack.

For each character:

• If it is "(", push it.
• If it is ")" and the stack has "(", pop one.
• Otherwise, this ")" is unmatched and needs one inserted "(".

At the end, every remaining "(" in the stack needs one inserted ")".

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

        for ch in s:
            if ch == "(":
                stack.append(ch)
            else:
                if stack:
                    stack.pop()
                else:
                    insertions += 1

        return insertions + len(stack)

This works, but the stack only stores how many unmatched opening parentheses exist.

So we can replace it with a counter.

Key Insight

Only two values matter:

When we see "(", it needs a future closing parenthesis:

open_needed += 1

When we see ")":

• If open_needed > 0, match it with one previous "(".
• Otherwise, this closing parenthesis has no opener, so we must insert "(".

After processing the whole string, any remaining open_needed must be closed by inserting ")".

Algorithm

1. Set open_needed = 0.
2. Set insertions = 0.
3. For every character in s:
   • If it is "(", increment open_needed.
   • Otherwise:
     • If open_needed > 0, decrement open_needed.
     • Else, increment insertions.
4. Return:

insertions + open_needed

Correctness

When the algorithm sees "(", it records that this opening parenthesis still needs a matching closing parenthesis.

When it sees ")" and open_needed > 0, matching it with the most recent unmatched opening parenthesis is always valid. This reduces the number of unmatched openings by one.

When it sees ")" and open_needed == 0, there is no earlier opening parenthesis that can match it. The only way to make this character valid is to insert an opening parenthesis before it. So increasing insertions is necessary and optimal.

After the scan, every remaining unmatched "(" needs exactly one inserted ")". There is no cheaper way to close them.

Thus the algorithm counts exactly the required insertions and returns the minimum.

Complexity

Implementation

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

        for ch in s:
            if ch == "(":
                open_needed += 1
            else:
                if open_needed > 0:
                    open_needed -= 1
                else:
                    insertions += 1

        return insertions + open_needed

Code Explanation

Track unmatched opening parentheses:

open_needed = 0

Track insertions needed for unmatched closing parentheses:

insertions = 0

An opening parenthesis waits for a future close:

if ch == "(":
    open_needed += 1

A closing parenthesis can match a previous opening parenthesis:

if open_needed > 0:
    open_needed -= 1

If there is no previous opening parenthesis, we need to insert one:

else:
    insertions += 1

At the end, remaining openings need closing parentheses:

return insertions + open_needed

Testing

def run_tests():
    s = Solution()

    assert s.minAddToMakeValid("())") == 1
    assert s.minAddToMakeValid("(((") == 3
    assert s.minAddToMakeValid("()") == 0
    assert s.minAddToMakeValid("()))((") == 4
    assert s.minAddToMakeValid(")") == 1
    assert s.minAddToMakeValid("(") == 1
    assert s.minAddToMakeValid(")()(") == 2

    print("all tests passed")

run_tests()

Test meaning: