LeetCode 921 - Minimum Add to Make Parentheses Valid

Difficulty: 🟡 Medium
Topics: String, Stack, Greedy

Solution

Problem Understanding

The problem asks us to determine the minimum number of parentheses insertions required to make a given string of parentheses valid. A string of parentheses is considered valid if every opening parenthesis '(' has a matching closing parenthesis ')' and the pairs are properly nested.

The input s is a string consisting only of '(' and ')', and the length is guaranteed to be between 1 and 1000. The expected output is a single integer representing the minimum number of parentheses that need to be added at any position in the string to make it valid.

Important edge cases include strings that are already balanced (no insertions needed), strings with only opening or only closing parentheses (requiring insertions equal to the string length), and alternating or nested unbalanced sequences. The problem guarantees that we only have '(' and ')' characters, so we do not need to handle invalid characters.

Approaches

The brute-force approach would involve generating all possible strings by inserting parentheses in every possible position until the string becomes valid. This approach is correct because it eventually explores all valid configurations, but it is extremely inefficient. The number of insertions grows combinatorially with the string length, making this approach infeasible for strings of length up to 1000.

The optimal approach relies on counting unmatched parentheses using a greedy method. We can traverse the string while keeping track of the number of unmatched opening and closing parentheses. When encountering '(', we increment a counter for open parentheses. When encountering ')', we either match it with a previously seen '(' if available or increment a counter for unmatched closing parentheses. The sum of unmatched opening and closing parentheses at the end gives the minimum number of insertions required.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Generates all valid strings by inserting parentheses until valid
Optimal	O(n)	O(1)	Counts unmatched parentheses in one pass using constant extra space

Algorithm Walkthrough

Initialize two counters: open_needed to track unmatched '(' and close_needed to track unmatched ')'.
Iterate through each character in the string s.
If the character is '(', increment open_needed because we have an extra opening parenthesis that needs a match.
If the character is ')', check if there is an unmatched '(' to pair with. If open_needed > 0, decrement open_needed to match this closing parenthesis. Otherwise, increment close_needed because we have an unmatched closing parenthesis.
After processing all characters, the total number of insertions required is open_needed + close_needed.
Return this sum as the result.

Why it works: The algorithm maintains the invariant that open_needed always represents the number of unmatched opening parentheses up to the current point in the string, and close_needed counts unmatched closing parentheses. By the end of the iteration, their sum correctly reflects the minimum insertions needed to balance all parentheses.

Python Solution

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        open_needed = 0
        close_needed = 0
        
        for char in s:
            if char == '(':
                open_needed += 1
            else:  # char == ')'
                if open_needed > 0:
                    open_needed -= 1
                else:
                    close_needed += 1
        
        return open_needed + close_needed

The code defines two counters for unmatched parentheses. Each character in the string is processed sequentially, updating these counters according to whether it is an opening or closing parenthesis. The final sum of unmatched openings and closings is returned.

Go Solution

func minAddToMakeValid(s string) int {
    openNeeded := 0
    closeNeeded := 0

    for _, char := range s {
        if char == '(' {
            openNeeded++
        } else { // char == ')'
            if openNeeded > 0 {
                openNeeded--
            } else {
                closeNeeded++
            }
        }
    }

    return openNeeded + closeNeeded
}

The Go implementation mirrors the Python logic. We use integer counters for unmatched parentheses and iterate over the string using a range loop. Go automatically handles rune iteration, so the logic remains straightforward.

Worked Examples

Example 1: s = "())"

Step	Char	open_needed	close_needed
1	'('	1	0
2	')'	0	0
3	')'	0	1

Result: 0 + 1 = 1

Example 2: s = "((("

Step	Char	open_needed
1	'('	1
2	'('	2
3	'('	3

Result: 3 + 0 = 3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate through the string exactly once, performing constant-time operations per character
Space	O(1)	Only two integer counters are used, independent of input size

The algorithm is extremely efficient because it only requires a single pass over the input and uses constant extra space.

Test Cases

# Provided examples
assert Solution().minAddToMakeValid("())") == 1  # one ')' needs matching '('
assert Solution().minAddToMakeValid("(((") == 3  # three '(' need closing ')'

# Additional cases
assert Solution().minAddToMakeValid("") == 0  # empty string is valid
assert Solution().minAddToMakeValid("()") == 0  # already balanced
assert Solution().minAddToMakeValid(")(") == 2  # needs one '(' at start and one ')' at end
assert Solution().minAddToMakeValid("(()") == 1  # one '(' unmatched
assert Solution().minAddToMakeValid("())(()") == 2  # one ')' unmatched, one '(' unmatched
assert Solution().minAddToMakeValid("(((((((((") == 9  # all '(' need closing ')'
assert Solution().minAddToMakeValid("))))))))") == 8  # all ')' need opening '('

Test	Why
"())"	Handles unmatched closing parenthesis
"((("	Handles unmatched opening parentheses
""	Valid empty string
"()"	Already valid string
")("	Completely reversed unmatched parentheses
"(()"	Single unmatched opening
"())(()"	Mixed unmatched parentheses
"((((((((("	Long string of only opening parentheses
"))))))))"	Long string of only closing parentheses

Edge Cases

One important edge case is a string with alternating parentheses like ")()(". This case tests whether the algorithm correctly handles unmatched parentheses at both the beginning and end of the string. The implementation correctly increments close_needed at the start and open_needed at the end.

Another edge case is a string composed entirely of one type of parenthesis, either all '(' or all ')'. Without careful counting, one might incorrectly assume partial matches exist. The counters approach ensures that each unmatched parenthesis is counted accurately.

A third edge case is an empty string. Even though there are no characters, the algorithm correctly returns 0 because no insertions are needed. Handling this correctly ensures robustness for minimal input sizes.