Code Logo

Minimum Add to Make Parentheses Valid

Published at25 Jul 2026
Created by
Medium 0 views
Like0

Given a string containing only parentheses '(' and ')', determine the minimum number of parentheses you must add to make the string valid. A valid parentheses string has every opening parenthesis matched with a closing one in the correct order.

For example, "())" needs 1 addition: add '(' at the front to get "(())". "(((" needs 3 additions: add ")))" at the end. "()" needs 0 additions. An empty string needs 0.

This problem teaches stack-based or counter-based parentheses balancing. It is a simpler version of the classic valid-parentheses problem, focusing on counting unmatched parentheses rather than validating intermediate states.

The solution uses a counter: iterate through each character. If it is '(', increment the counter. If it is ')' and the counter is positive, decrement it (matching a previous '('). If it is ')' and the counter is zero, increment a needed counter (this ')' is unmatched). The total additions needed is the sum of the final counter (unmatched '(') and the needed counter (unmatched ')').

Edge cases include an empty string (return 0), only opening parentheses (return the count), only closing parentheses (return the count), and already-valid strings (return 0).

Example Input & Output

Example 1
Input
"()))(("
Output
4
Explanation

2 to close, 2 to open

Example 2
Input
"())"
Output
1
Explanation

Add one '(' at start

Example 3
Input
""
Output
0
Explanation

Empty is valid

Example 4
Input
"()"
Output
0
Explanation

Already valid

Example 5
Input
"((("
Output
3
Explanation

Add three ')' at end

Algorithm Flow

Recommendation Algorithm Flow for Minimum Add to Make Parentheses Valid

Solution Approach

Use a counter to track unmatched opening parentheses and count unmatched closing ones.

function minAdd(s)
  open = 0, add = 0
  for i = 0 to length(s) - 1
    if s[i] == '(' then open = open + 1
    else if open > 0 then open = open - 1
    else add = add + 1
  return open + add

Track open parentheses with a counter. For '(' increment open. For ')', if there is an open parenthesis to match, decrement open. Otherwise, this ')' is unmatched — increment add. The total additions needed is open + add: open unmatched '(' plus add unmatched ')'.

Time complexity is O(n), space complexity is O(1).

Best Answers

java
class Solution {
    public int solution(String s) {
        int add=0,bal=0;
        for(int i=0;i<s.length();i++){char c=s.charAt(i);
            if(c=='(')bal++;
            else if(bal>0)bal--;
            else add++;
        }return add+bal;
    }
}