Approach: Track open and needed

def minAddToMakeValid(s):
    open_ = add = 0
    for c in s:
        if c == "(": open_ += 1
        elif open_ > 0: open_ -= 1
        else: add += 1
    return add + open_

Complexity: O(n) time, O(1) space.

Full Solution — all languages

class Solution:
    def minAddToMakeValid(self, s):
        open_ = add = 0
        for c in s:
            if c == "(":
                open_ += 1
            elif open_ > 0:
                open_ -= 1
            else:
                add += 1
        return add + open_

import java.util.*;
class Solution {
    public int minAddToMakeValid(String s) {
        int open = 0, add = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') open++;
            else if (open > 0) open--;
            else add++;
        }
        return add + open;
    }
}

#include <bits/stdc++.h> using namespace std;
class Solution {
    public: int minAddToMakeValid(string s) {
        int open = 0, add = 0;
        for (char c : s) {
            if (c == '(') open++;
            else if (open > 0) open--;
            else add++;
        }
        return add + open;
    }
};

/**
 * @param {string} s
 * @return {number}
 */ var minAddToMakeValid = function(s) {
    let open = 0, add = 0;
    for (const c of s) {
        if (c === '(') open++;
        else if (open > 0) open--;
        else add++;
    }
    return add + open;
};

Minimum Add to Make Parentheses Valid

Example 1

Example 2

Example 3

Constraints