Minimum add to make parentheses valid

String Stack Greedy

74.4% acceptance

Feb 25, 2026

4928

247

A parentheses string is valid if and only if: It is the empty string, It can be written as AB (A concatenated with B), where A and B are valid strings, or It can be written as (A), where A is a valid string. You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string. For example, if s = "()))", you can insert an opening parenthesis to be "(()))" or a closing parenthesis to be "())))". Return the minimum number of moves required to make s valid.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_add_to_make_valid(s: String) -> i32 {
    let (mut open, mut close) = (0, 0);
    for c in s.chars() {
      if c == '(' { open += 1; } else if open > 0 { open -= 1; } else { close += 1; }
    }
    open + close
  }
}