Code Logo

Minimum Add to Make Parentheses Valid

Published at25 Jul 2026
Created by
Medium 0 views
Like0

Given a string s of '(' and ')' parentheses, return the minimum number of parentheses you must add to make the resulting string valid. A valid parentheses string has every '(' matched with a corresponding ')' in the correct order.

Track the balance as you iterate. When you see '(', increment balance. When you see ')', if balance > 0, decrement it (matching a previous '('), otherwise increment the add count (we need to add a matching '('). After the loop, the remaining balance is the number of ')' needed to close unmatched '('.

Time complexity is O(n) and space is O(1). This greedy approach works because parentheses can only be matched in order, so we never need to reconsider decisions.

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
Recommendation Algorithm Flow for Minimum Add to Make Parentheses Valid

Solution Approach

function solution(s) {
  var add = 0, bal = 0;
  for (var i = 0; i < s.length; i++) {
    if (s.charAt(i) === '(') bal++;
    else if (bal > 0) bal--;
    else add++;
  }
  return add + bal;
}

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;
    }
}