Remove invalid parentheses

String Backtracking Breadth-First Search

49.8% acceptance

Jan 12, 2026

6063

302

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid. Return a list of unique strings that are valid with the minimum number of removals. You may return the answer in any order.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn remove_invalid_parentheses(s: String) -> Vec<String> {
    use std::collections::{HashSet, VecDeque};
    
    let is_valid = |s: &str| -> bool {
      let mut count = 0;
      for ch in s.chars() {
        if ch == '(' {
          count += 1;
        } else if ch == ')' {
          count -= 1;
          if count < 0 {
            return false;
          }
        }
      }
      count == 0
    };
    
    let mut result = Vec::new();
    let mut visited = HashSet::new();
    let mut queue = VecDeque::new();
    
    queue.push_back(s.clone());
    visited.insert(s.clone());
    let mut found = false;
    
    while !queue.is_empty() {
      let curr = queue.pop_front().unwrap();
      
      if is_valid(&curr) {
        result.push(curr.clone());
        found = true;
      }
      
      if found {
        continue;
      }
      
      for i in 0..curr.len() {
        if curr.chars().nth(i).unwrap() != '(' && curr.chars().nth(i).unwrap() != ')' {
          continue;
        }
        
        let next = format!("{}{}", &curr[..i], &curr[i+1..]);
        if !visited.contains(&next) {
          visited.insert(next.clone());
          queue.push_back(next);
        }
      }
    }
    
    result
  }
}