Delete Duplicate Folders in System

hard trie hashing dfs serialization

Problem

You are given a list of absolute folder paths, where each path is a list of folder names (so ["one","two"] means /one/two). Two folders are identical if they contain the same non-empty set of subfolders with the same underlying structure — regardless of depth. Mark every group of two or more identical folders together with all of their subfolders, then delete all marked folders in a single pass. Return the paths of the folders that remain (in any order).

Inputpaths = [["a"],["c"],["d"],["a","b"],["c","b"],["d","a"]]

Output[["d"],["d","a"]]

Folders /a and /c are identical — each holds one empty child b — so both subtrees are deleted. Only /d and /d/a survive.

paths (one path per line, slash-separated)

def deleteDuplicateFolder(paths):
    root = {}                                   # trie: name -> child dict
    for path in paths:                          # build the folder trie
        node = root
        for name in path:
            node = node.setdefault(name, {})

    count = {}                                   # signature -> occurrences
    sig = {}                                     # id(node) -> its signature

    def serialize(node):                        # post-order canonical string
        if not node:
            return ""                           # leaf: empty, never marked
        parts = []
        for name in sorted(node):
            parts.append(name + "(" + serialize(node[name]) + ")")
        s = "".join(parts)
        sig[id(node)] = s
        count[s] = count.get(s, 0) + 1          # tally identical structures
        return s

    serialize(root)                             # root counted but never deleted

    ans = []
    def build(node, path):                      # collect surviving paths
        for name in sorted(node):
            child = node[name]
            s = sig.get(id(child), "")
            if s and count[s] >= 2:             # duplicate -> skip subtree
                continue
            path.append(name)
            ans.append(path[:])
            build(child, path)
            path.pop()

    build(root, [])
    return ans

function deleteDuplicateFolder(paths) {
  const root = new Map();                       // trie: name -> child Map
  for (const path of paths) {                   // build the folder trie
    let node = root;
    for (const name of path) {
      if (!node.has(name)) node.set(name, new Map());
      node = node.get(name);
    }
  }

  const count = new Map();                       // signature -> occurrences
  const sig = new Map();                         // node -> its signature

  function serialize(node) {                     // post-order canonical string
    if (node.size === 0) return "";              // leaf: empty, never marked
    const parts = [];
    for (const name of [...node.keys()].sort())
      parts.push(name + "(" + serialize(node.get(name)) + ")");
    const s = parts.join("");
    sig.set(node, s);
    count.set(s, (count.get(s) || 0) + 1);       // tally identical structures
    return s;
  }
  serialize(root);                               // root counted, never deleted

  const ans = [];
  function build(node, path) {                   // collect surviving paths
    for (const name of [...node.keys()].sort()) {
      const child = node.get(name);
      const s = sig.get(child) || "";
      if (s && count.get(s) >= 2) continue;       // duplicate -> skip subtree
      path.push(name);
      ans.push(path.slice());
      build(child, path);
      path.pop();
    }
  }
  build(root, []);
  return ans;
}

List<List<String>> deleteDuplicateFolder(List<List<String>> paths) {
    Map<String, Object> root = new HashMap<>(); // trie: name -> child map
    for (List<String> path : paths) {           // build the folder trie
        Map<String, Object> node = root;
        for (String name : path)
            node = (Map<String, Object>) node.computeIfAbsent(name, k -> new HashMap<>());
    }

    Map<String, Integer> count = new HashMap<>();          // signature -> occurrences
    Map<Map<String, Object>, String> sig = new IdentityHashMap<>();

    serialize(root, count, sig);                // root counted, never deleted

    List<List<String>> ans = new ArrayList<>();
    build(root, new ArrayList<>(), ans, count, sig);
    return ans;
}

String serialize(Map<String, Object> node,
                 Map<String, Integer> count,
                 Map<Map<String, Object>, String> sig) {
    if (node.isEmpty()) return "";              // leaf: empty, never marked
    StringBuilder sb = new StringBuilder();
    for (String name : new TreeSet<>(node.keySet())) {
        Map<String, Object> child = (Map<String, Object>) node.get(name);
        sb.append(name).append("(").append(serialize(child, count, sig)).append(")");
    }
    String s = sb.toString();
    sig.put(node, s);
    count.merge(s, 1, Integer::sum);            // tally identical structures
    return s;
}

void build(Map<String, Object> node, List<String> path,
           List<List<String>> ans, Map<String, Integer> count,
           Map<Map<String, Object>, String> sig) {
    for (String name : new TreeSet<>(node.keySet())) {
        Map<String, Object> child = (Map<String, Object>) node.get(name);
        String s = sig.getOrDefault(child, "");
        if (!s.isEmpty() && count.get(s) >= 2) continue; // duplicate -> skip
        path.add(name);
        ans.add(new ArrayList<>(path));
        build(child, path, ans, count, sig);
        path.remove(path.size() - 1);
    }
}

struct Node { map<string, Node*> ch; string sig; };

unordered_map<string, int> count;               // signature -> occurrences

string serialize(Node* node) {                  // post-order canonical string
    if (node->ch.empty()) return "";            // leaf: empty, never marked
    string s;
    for (auto& [name, child] : node->ch)        // map keeps names sorted
        s += name + "(" + serialize(child) + ")";
    node->sig = s;
    count[s]++;                                  // tally identical structures
    return s;
}

void build(Node* node, vector<string>& path, vector<vector<string>>& ans) {
    for (auto& [name, child] : node->ch) {      // map keeps names sorted
        if (!child->sig.empty() && count[child->sig] >= 2) continue; // skip dup
        path.push_back(name);
        ans.push_back(path);
        build(child, path, ans);
        path.pop_back();
    }
}

vector<vector<string>> deleteDuplicateFolder(vector<vector<string>>& paths) {
    Node* root = new Node();                     // build the folder trie
    for (auto& path : paths) {
        Node* node = root;
        for (auto& name : path) {
            if (!node->ch.count(name)) node->ch[name] = new Node();
            node = node->ch[name];
        }
    }
    serialize(root);                             // root counted, never deleted
    vector<vector<string>> ans; vector<string> path;
    build(root, path, ans);
    return ans;
}

Explanation

The folders form a tree, so the first move is to build a trie: insert every path one name at a time, and each node owns a map from child name to child node. After this, the whole file system is one rooted tree.

Two folders are identical when their subtree shapes match. To compare shapes cheaply we give each subtree a canonical signature string. Working bottom-up (post-order), a node's signature is the concatenation of name(childSignature) for its children in sorted order. Sorting makes the signature order-independent, so two folders with the same children produce the exact same string.

A leaf (a folder with no subfolders) serializes to the empty string. We deliberately never count empty signatures, because the rule only marks folders that share a non-empty structure — two empty folders are not "identical" for deletion purposes.

While serializing we keep a hash map count from signature to how many times it appears. Any signature with count >= 2 belongs to a duplicated structure, so every node carrying that signature is marked.

Finally we walk the trie again from the root. Whenever we reach a child whose signature is duplicated, we skip its entire subtree (the children inherit the deletion automatically). Every other folder we visit contributes its current path to the answer. Because all duplicates are identified before any pruning, folders that only become identical after deletion are correctly left untouched.

Example: [["a"],["c"],["d"],["a","b"],["c","b"],["d","a"]]. Both /a and /c serialize to b(), so count["b()"] = 2 and both are deleted. /d serializes to a() with count 1, so /d and /d/a survive.

Time: O(N · L · log L) Space: O(N · L)