Delete duplicate folders in system

Array Hash Table String Trie Hash Function

77.7% acceptance

Feb 25, 2026

618

142

Due to a bug, there are many duplicate folders in a file system. You are given a 2D array paths, where paths[i] is an array representing an absolute path to the ith folder in the file system. For example, ["one", "two", "three"] represents the path "/one/two/three". Two folders (not necessarily on the same level) are identical if they contain the same non-empty set of identical subfolders and underlying subfolder structure. The folders do not need to be at the root level to be identical. If two or more folders are identical, then mark the folders as well as all their subfolders. Once all the identical folders and their subfolders have been marked, the file system will delete all of them. The file system only runs the deletion once, so any folders that become identical after the initial deletion are not deleted. Return the 2D array ans containing the paths of the remaining folders after deleting all the marked folders. The paths may be returned in any order.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn delete_duplicate_folder(paths: Vec<Vec<String>>) -> Vec<Vec<String>> {
    // Build trie
    let mut trie: Vec<HashMap<String, usize>> = vec![HashMap::new()]; // node 0 is root

    for path in &paths {
      let mut node = 0;
      for name in path {
        let next = trie.len();
        if !trie[node].contains_key(name) {
          trie[node].insert(name.clone(), next);
          trie.push(HashMap::new());
        }
        node = trie[node][name];
      }
    }

    // Serialize each subtree and find duplicates
    let n = trie.len();
    let mut serial = vec![String::new(); n];
    let mut serial_count: HashMap<String, usize> = HashMap::new();

    // Process nodes in reverse order (post-order by construction is tricky, use DFS)
    fn build_serial(
      node: usize,
      trie: &[HashMap<String, usize>],
      serial: &mut Vec<String>,
      serial_count: &mut HashMap<String, usize>,
    ) {
      if trie[node].is_empty() {
        serial[node] = String::new();
        return;
      }
      let mut parts: Vec<String> = Vec::new();
      let mut children: Vec<(&String, &usize)> = trie[node].iter().collect();
      children.sort_by_key(|(name, _)| name.to_string());
      for (name, child) in &children {
        build_serial(**child, trie, serial, serial_count);
        parts.push(format!("({}{})", name, serial[**child]));
      }
      serial[node] = parts.join("");
      *serial_count.entry(serial[node].clone()).or_insert(0) += 1;
    }

    build_serial(0, &trie, &mut serial, &mut serial_count);

    // Mark nodes to delete (non-empty serial that appears more than once)
    let mut deleted = vec![false; n];
    fn mark_deleted(
      node: usize,
      trie: &[HashMap<String, usize>],
      serial: &[String],
      serial_count: &HashMap<String, usize>,
      deleted: &mut Vec<bool>,
    ) {
      if !serial[node].is_empty() && serial_count[&serial[node]] > 1 {
        deleted[node] = true;
        return;
      }
      for (_, child) in &trie[node] {
        mark_deleted(*child, trie, serial, serial_count, deleted);
      }
    }

    mark_deleted(0, &trie, &serial, &serial_count, &mut deleted);

    // Collect remaining paths
    let mut result = Vec::new();
    fn collect(
      node: usize,
      path: &mut Vec<String>,
      trie: &[HashMap<String, usize>],
      deleted: &[bool],
      result: &mut Vec<Vec<String>>,
    ) {
      for (name, child) in &trie[node] {
        if !deleted[*child] {
          path.push(name.clone());
          result.push(path.clone());
          collect(*child, path, trie, deleted, result);
          path.pop();
        }
      }
    }

    collect(0, &mut Vec::new(), &trie, &deleted, &mut result);
    result
  }
}