Minimum Add to make parentehses valid

921.Minimum Add to Make Parentheses Valid

String

Greedy

Counting

Problem Statement:

Given a string S of '(' and ')' parentheses, we add the minimum number of parentheses ( '(' or ')', and in any positions ) so that the resulting parentheses string is valid. Return the minimum number of parentheses we must add.

Example:

Input:

S = "())"

→

Output:

1

Java Solution:

public int minAddToMakeValid(String S) {
    int count = 0;  // Count of needed closing parentheses
    int open = 0;   // Count of unmatched opening parentheses
    
    for (int i = 0; i < S.length(); ++i) {
        if (S.charAt(i) == '(') 
            open++;  // Track open parentheses
        else if (S.charAt(i) == ')')
            if (open > 0) open--;  // Match with existing open
            else count++;  // Need an opening parenthesis
    }
    
    return count + open;  // Total needed = unmatched closing + unmatched opening
}

Python Solution:

def minAddToMakeValid(self, S: str) -> int:
    count = open_count = 0
    
    for char in S:
        if char == '(':
            open_count += 1
        else:
            if open_count > 0:
                open_count -= 1
            else:
                count += 1
                
    return count + open_count

C++ Solution:

class Solution {
public:
    int minAddToMakeValid(string S) {
        int count = 0, open = 0;
        
        for(char c : S) {
            if(c == '(')
                open++;
            else if(open > 0)
                open--;
            else
                count++;
        }
        
        return count + open;
    }
};

Complexity:

Time: O(n) | Space: O(1)