Why is this code 10x faster than mine?

My solution to Minimum Remove to Make Valid Parentheses(20ms):

pub fn min_remove_to_make_valid(s: String) -> String {
    let mut stack: Vec<usize> = vec![];
    let mut indices: HashSet<usize> = HashSet::new();

    for (i, c) in s.chars().enumerate() {
        if c == '(' {
            stack.push(i)
        } else if c == ')' && stack.pop().is_none() {
            indices.insert(i);
        }
    }

    indices.extend(stack);

    s.chars()
        .enumerate()
        .filter_map(|(i, c)| (!indices.contains(&i)).then_some(c))
        .collect()
}

2ms solution:

struct Letter {
    char: char,
    pos: usize,
}

pub fn min_remove_to_make_valid(s: String) -> String {
    let mut letters: Vec<char> = Vec::new();
    let mut reg: VecDeque<Letter> = VecDeque::new();

    for l in s.chars() {
        if l == '(' {
            letters.push('#');
            let letter: Letter = Letter {
                char: l,
                pos: letters.len() - 1,
            };
            reg.push_back(letter);
        } else if l == ')' {
            if !reg.is_empty() {
                let letter: Letter = reg.pop_back().unwrap();
                letters[letter.pos] = letter.char;
                letters.push(l);
            }
        } else {
            letters.push(l);
        }
    }

    let mut ans = String::new();

    for &char in letters.iter() {
        if char != '#' {
            ans.push(char);
        }
    }

    ans
}

I know I am doing some extra work building the string at the end - accessing the indices set for every character (I tried only checking if the character is ( or ), made no difference). But the 2ms solution is doing more work in the main loop - pushing something to a vector every loop iteration, and sometimes doing two or three accesses. Other than that, we both use two heap-allocated collections, and then build a new string at the end.

Any thoughts?