#921

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Minimum Add to Make Parentheses Valid

Compute the minimum insertions needed to make a parentheses string valid using efficient stack-based state tracking techniques.

string stack greedy

Problem Statement

You are given a string s consisting only of '(' and ')'. A string is considered valid if every opening parenthesis has a corresponding closing parenthesis and the pairs are properly nested. You may insert parentheses at any position in s to achieve validity.

Return the minimum number of parentheses insertions required to make s valid. For example, for s = "())", the minimum insertions is 1, and for s = "(((", the minimum insertions is 3. Optimize for a linear scan using stack-like state management.

Examples

Example 1

Input: s = "())"

Output: 1

Example details omitted.

Example 2

Input: s = "((("

Output: 3

Example details omitted.

Constraints

1 <= s.length <= 1000
s[i] is either '(' or ')'.

Solution Approach

Use a counter for unmatched opens

Iterate through s, incrementing an open counter for '(' and decrementing for ')'. When a ')' occurs without a matching '(', increment a separate insertion counter. This simulates a stack while keeping space O(1).

Calculate final required insertions

After scanning the string, any remaining open parentheses require corresponding ')' insertions. The total minimum insertions is the sum of unmatched closes counted during iteration and remaining opens at the end.

Optimize with Greedy single pass

By greedily inserting whenever an imbalance is detected, you avoid maintaining a full stack. This single-pass strategy aligns with the Stack-based state management pattern and ensures linear time performance.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

Time complexity is O(N) as each character is visited once. Space complexity is O(1) because only counters are maintained instead of an actual stack, making it optimal for large strings.

What Interviewers Usually Probe

Check if candidate handles both excess '(' and ')' correctly.
Listen for discussion of O(1) space using counters versus explicit stack.
Evaluate understanding of stack-based state tracking applied greedily.

Common Pitfalls or Variants

Common pitfalls

Failing to count unmatched ')' during iteration leading to undercounted insertions.
Using a full stack unnecessarily, increasing space usage.
Ignoring leftover '(' at the end of the string.

Follow-up variants

Compute minimum removals instead of insertions to make a parentheses string valid.
Apply the same stack-based method to strings containing other types of brackets.
Return the corrected valid string after minimal insertions rather than just the count.

FAQ

What pattern does Minimum Add to Make Parentheses Valid follow?

It follows the Stack-based state management pattern, where tracking unmatched parentheses determines minimum insertions.

Can this problem be solved without an explicit stack?

Yes, using counters for unmatched '(' and ')' achieves the same result with O(1) space.

Why is a single pass sufficient for this problem?

Each character's contribution to imbalance is independent, so tracking counters while scanning once captures all required insertions.

What common mistakes should be avoided?

Failing to account for leftover '(' at the end, ignoring unmatched ')', or unnecessarily using a full stack.

How does the greedy approach work here?

It inserts when an imbalance occurs rather than revisiting previous characters, ensuring minimum insertions efficiently.

terminal

Solution

Solution 1: Greedy + Stack

This problem is a classic parenthesis matching problem, which can be solved using "Greedy + Stack".

1

2

3

4

5

6

7

8

9

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

Solution 2: Greedy + Counting

Solution 1 uses a stack to implement parenthesis matching, but we can also directly implement it through counting.

1

2

3

4

5

6

7

8

9

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

Solution 3: Replace + recursion

#### TypeScript

1

2

3

4

5

6

7

8

9

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

Continue Practicing

#936 stamping the sequence #1081 smallest subsequence of distinct characters #678 valid parenthesis string