Minimum remove to make valid parentheses

String Stack

71.3% acceptance

Feb 25, 2026

7372

167

Given a string s of '(' , ')' and lowercase English characters. Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string. Formally, a parentheses string is valid if and only if: It is the empty string, contains only lowercase characters, or 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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_remove_to_make_valid(s: String) -> String {
    let chars: Vec<char> = s.chars().collect();
    let mut stack: Vec<usize> = Vec::new(); // indices of unmatched '('
    let mut to_remove: std::collections::HashSet<usize> = std::collections::HashSet::new();

    for (i, &c) in chars.iter().enumerate() {
      if c == '(' {
        stack.push(i);
      } else if c == ')' {
        if let Some(_) = stack.pop() {
          // matched
        } else {
          to_remove.insert(i);
        }
      }
    }
    for i in stack {
      to_remove.insert(i);
    }

    chars.iter().enumerate()
      .filter(|(i, _)| !to_remove.contains(i))
      .map(|(_, &c)| c)
      .collect()
  }
}