Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Minimum Add to Make Parentheses Valid

MEDIUMProblemSolveExternal Links

Description

A parentheses string is valid if and only if:

  • It is the empty string, or
  • It can be written as AB where A and B are both valid parentheses strings, or
  • It can be written as (A) where A is a valid parentheses string.

Given a parentheses string s consisting of '(' and ')' characters only, return the minimum number of parentheses you must add to make the resulting string valid.

You may insert a parenthesis at any position in the string.

Examples

Example 1

Input: s = "())"

Output: 1

Explanation: The string has two closing brackets but only one opening bracket. The first '(' and the first ')' form a valid pair. The second ')' at index 2 is unmatched — it needs an '(' inserted before it. One addition makes the string valid (for example, "(())").

Example 2

Input: s = "((("

Output: 3

Explanation: All three characters are opening brackets with no closing brackets to match them. Each '(' needs a corresponding ')' inserted after it. Three additions are required (for example, "((()))").

Example 3

Input: s = "())("

Output: 2

Explanation: Processing left to right: '(' and the first ')' form a valid pair. The second ')' at index 2 has no matching opener — needs one '(' added before it. The '(' at index 3 has no matching closer — needs one ')' added after it. Two additions total.

Constraints

  • 1 ≤ s.length ≤ 1000
  • s[i] is either '(' or ')'

Editorial

Brute Force

Intuition

The simplest way to think about this problem is: a matching pair "()" is self-sufficient and needs no additions. If we remove all such pairs, whatever characters remain are unmatched and each one needs exactly one partner.

Imagine a game of musical chairs where every '(' seeks a ')' sitting directly beside it. When a match is found, both leave the room. We keep running rounds of this game until no adjacent "()" pairs remain. The people left in the room are unmatched, and each one needs a new partner brought in.

Concretely: repeatedly scan the string for the substring "()" and remove it. When no more "()" can be found, the length of the remaining string is the answer.

Step-by-Step Explanation

Let's trace through with s = "())(":

Step 1: Start with s = "())(".

Step 2: Pass 1 — scan for adjacent "()". Found at indices 0–1: the '(' at index 0 and ')' at index 1 form a valid pair.

Step 3: Remove the pair. The string becomes ")(".

Step 4: Pass 2 — scan for adjacent "()". Check indices 0–1: ')' followed by '(' is not a valid pair.

Step 5: No "()" found anywhere. The removal process terminates.

Step 6: The remaining string ")( " has length 2. Every remaining character is unmatched.

Step 7: Answer: 2 parentheses must be added (one ')' after the '(' and one '(' before the ')' — or equivalently any valid insertion strategy).

Repeated Pair Removal on "())(" — Watch how we repeatedly scan for adjacent matching pairs and remove them until no pairs remain. The leftover characters are all unmatched.

Algorithm

  1. Repeat until no changes occur:
    • Scan the string for the substring "()"
    • If found, remove it (replace with empty string)
  2. Return the length of the remaining string

Code

class Solution {
public:
    int minAddToMakeValid(string s) {
        size_t pos;
        while ((pos = s.find("()")) != string::npos) {
            s.erase(pos, 2);
        }
        return s.size();
    }
};
class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        while "()" in s:
            s = s.replace("()", "", 1)
        return len(s)
class Solution {
    public int minAddToMakeValid(String s) {
        while (s.contains("()")) {
            s = s.replace("()", "");
        }
        return s.length();
    }
}

Complexity Analysis

Time Complexity: O(n²)

Each pass scans the string in O(n) time and removes at most one pair (shrinking the string by 2). In the worst case (e.g., "(((...)))" with n/2 pairs removed one at a time), we perform roughly n/2 passes, each costing O(n). Total: O(n²).

Space Complexity: O(n)

String operations may create a new copy of the string at each removal step. The maximum string length at any point is n.

Why This Approach Is Not Efficient

The repeated pair removal approach rescans the string from the beginning after every single removal. For a string like "(((())))" (4 opens then 4 closes), the innermost pair is found and removed first, then the next innermost, and so on — requiring 4 passes over the shrinking string.

The core inefficiency is that we revisit characters we have already examined. When we find a match, we should be able to handle it immediately and continue forward, not restart.

Key insight: a stack lets us process the string in a single left-to-right pass. When we encounter ')', we check if the most recent unmatched character was '(' — if so, they match and we pop. This eliminates the need for repeated scanning.

Better Approach - Stack-Based Matching

Intuition

Instead of removing pairs from the string, we can use a stack to track unmatched parentheses in a single pass:

  • When we see '(', push it onto the stack. It is "waiting" for a future ')' to match with.
  • When we see ')', check the top of the stack:
    • If the top is '(', they form a valid pair — pop the '(' off the stack.
    • Otherwise (stack is empty or top is ')'), this ')' is unmatched — push it.

After processing every character, the stack holds exactly the unmatched parentheses. Each unmatched character needs one partner inserted, so the answer is simply the stack size.

Think of the stack as a waiting room. Opening brackets wait in line for a closing bracket to arrive. When a closing bracket appears, it takes the most recent opening bracket from the front of the line. If no opening bracket is waiting, the closing bracket itself joins the line as permanently unmatched.

Step-by-Step Explanation

Let's trace through with s = "())(":

Step 1: Initialize empty stack. Begin processing s = "())(" from left to right.

Step 2: Read '(' at index 0. It is an opening bracket — push onto stack. Stack: ['('].

Step 3: Read ')' at index 1. Check stack: top is '(' — match found! Pop '(' from stack. Stack: [].

Step 4: Read ')' at index 2. Check stack: stack is empty — no '(' available to match. This ')' is unmatched. Push ')'. Stack: [')'].

Step 5: Read '(' at index 3. It is an opening bracket — push. Stack: [')', '('].

Step 6: All characters processed. Stack contains 2 unmatched items: ')' and '('.

Step 7: Each unmatched character needs one insertion. Answer: stack size = 2.

Stack-Based Matching on "())(" — Watch how the stack collects unmatched parentheses. Opening brackets are pushed, and closing brackets either pop a matching opener or get pushed themselves.

Algorithm

  1. Initialize an empty stack
  2. For each character c in s:
    • If c is ')' AND the stack is not empty AND the top of the stack is '(':
      • Pop the top of the stack (matched pair)
    • Otherwise:
      • Push c onto the stack (unmatched character)
  3. Return the size of the stack

Code

class Solution {
public:
    int minAddToMakeValid(string s) {
        stack<char> stk;
        for (char c : s) {
            if (c == ')' && !stk.empty() && stk.top() == '(') {
                stk.pop();
            } else {
                stk.push(c);
            }
        }
        return stk.size();
    }
};
class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        stack = []
        for char in s:
            if char == ')' and stack and stack[-1] == '(':
                stack.pop()
            else:
                stack.append(char)
        return len(stack)
class Solution {
    public int minAddToMakeValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == ')' && !stack.isEmpty() && stack.peek() == '(') {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        return stack.size();
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the string exactly once. Each character triggers at most one stack operation (push or pop), both of which are O(1). Total: n iterations × O(1) work = O(n).

Space Complexity: O(n)

In the worst case (e.g., s = "(((..." or s = ")))..."), every character is unmatched and pushed onto the stack, consuming O(n) space.

Why This Approach Is Not Efficient

The stack approach is already O(n) in time, which is optimal since we must examine every character at least once. However, it uses O(n) space for the stack, which is unnecessary.

Notice what the stack actually stores: unmatched '(' characters and unmatched ')' characters. But we never need to inspect characters deep inside the stack — we only ever look at the top. Moreover, all unmatched ')' characters are pushed before any unmatched '(' characters (because once we push a ')', no future '(' can match it — matching only works in the forward direction).

This means we can replace the entire stack with just two integer counters: one counting unmatched opening brackets and one counting unmatched closing brackets. This eliminates the O(n) space overhead.

Optimal Approach - Two Counters

Intuition

We can observe that we never need the actual contents of the stack — only how many unmatched openers and closers exist. This lets us replace the stack with two simple counters:

  • open_unmatched — counts '(' characters that have not yet found a matching ')'
  • close_unmatched — counts ')' characters that could not find a preceding '('

When we encounter '(', increment open_unmatched — this opener is waiting for a closer.
When we encounter ')':

  • If open_unmatched > 0, a waiting opener can absorb this closer — decrement open_unmatched.
  • Otherwise, no opener is available — increment close_unmatched.

After processing all characters, every unmatched opener needs one ')' and every unmatched closer needs one '('. The answer is open_unmatched + close_unmatched.

This is like counting debts: each '(' creates a debt that a ')' can pay off. Unpaid debts at the end are the answer.

Step-by-Step Explanation

Let's trace through with s = "())(":

Step 1: Initialize open_unmatched = 0, close_unmatched = 0.

Step 2: Read '(' at index 0. Increment open_unmatched to 1. One opener waiting.

Step 3: Read ')' at index 1. open_unmatched > 0 — a waiting opener can match! Decrement open_unmatched to 0. Pair matched.

Step 4: Read ')' at index 2. open_unmatched = 0 — no opener available. Increment close_unmatched to 1. This closer is permanently stranded.

Step 5: Read '(' at index 3. Increment open_unmatched to 1. This opener has no future closer (end of string).

Step 6: All characters processed. open_unmatched = 1, close_unmatched = 1.

Step 7: Answer: 1 + 1 = 2.

Two-Counter Scan on "())(" — Watch how two integer counters replace the entire stack. Opening brackets increment the open counter; closing brackets either decrement it or increment the close counter.

Algorithm

  1. Initialize two counters: open_unmatched = 0, close_unmatched = 0
  2. For each character c in s:
    • If c is '(':
      • Increment open_unmatched
    • Else (c is ')'):
      • If open_unmatched > 0: decrement open_unmatched (matched pair)
      • Else: increment close_unmatched (unmatched closer)
  3. Return open_unmatched + close_unmatched

Code

class Solution {
public:
    int minAddToMakeValid(string s) {
        int openUnmatched = 0, closeUnmatched = 0;
        for (char c : s) {
            if (c == '(') {
                openUnmatched++;
            } else {
                if (openUnmatched > 0) {
                    openUnmatched--;
                } else {
                    closeUnmatched++;
                }
            }
        }
        return openUnmatched + closeUnmatched;
    }
};
class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        open_unmatched = 0
        close_unmatched = 0
        for char in s:
            if char == '(':
                open_unmatched += 1
            else:
                if open_unmatched > 0:
                    open_unmatched -= 1
                else:
                    close_unmatched += 1
        return open_unmatched + close_unmatched
class Solution {
    public int minAddToMakeValid(String s) {
        int openUnmatched = 0, closeUnmatched = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                openUnmatched++;
            } else {
                if (openUnmatched > 0) {
                    openUnmatched--;
                } else {
                    closeUnmatched++;
                }
            }
        }
        return openUnmatched + closeUnmatched;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the string exactly once. Each character involves at most one comparison and one counter update, both O(1). Total: O(n).

Space Complexity: O(1)

We use only two integer variables (open_unmatched and close_unmatched) regardless of the input size. This is a constant-space improvement over the stack-based approach, which uses O(n) space in the worst case.