1249. Minimum Remove to Make Valid Parentheses

[jason89521]

Practice Dates

• 2024/05/14

Description

Link: https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/description/

Solution

impl Solution {
    pub fn min_remove_to_make_valid(s: String) -> String {
        let mut left_stack = vec![];
        let mut remove_set = std::collections::HashSet::new();
        for (idx, ch) in s.chars().enumerate() {
            if ch == '(' {
                left_stack.push(idx);
            } else if ch == ')' {
                if let Some(left) = left_stack.last() {
                    left_stack.pop();
                } else {
                    remove_set.insert(idx);
                }
            } else {
            }
        }

        for &idx in left_stack.iter() {
            remove_set.insert(idx);
        }

        s.chars().enumerate().fold(String::from(""), |mut acc, (idx, ch)| {
            if !remove_set.contains(&idx) {
                acc.push(ch);
            } 
            acc
        })
    }
}

Performance

Time complexity: