Java Trie + HashMap + StringBuilder 99 ms faster than 100%
\nclass Node\n{\n    String s; // Value of node (folder name)\n    String encoded; // Encoded subtree including and below current node\n    Map<String, Node> ch
```\nclass Node\n{\n    String s; // Value of node (folder name)\n    String encoded; // Encoded subtree including and below current node\n    Map<String, Node> children; // N-ary tree so children taken as hashmap\n    Node()\n    {\n        this.encoded = "";\n        this.s = "";\n        this.children = new HashMap<>();\n    }\n    Node(String s)\n    {\n        this.encoded = "";\n        this.s = s;\n        this.children = new HashMap<>();\n    }\n}\nclass Solution\n{\n    Map<String, Integer> freq; // Store frequencies of encoded subtrees\n    public List<List<String>> deleteDuplicateFolder(List<List<String>> paths)\n    {\n        Node root = new Node(); // root node of trie\n        for(List<String> path : paths)\n            addPath(root, path); // Add all paths to the trie\n        freq = new HashMap<>();\n        buildHash(root); // Function to find frequency of all subtrees\n        List<List<String>> ans = new ArrayList<>(); // Store the required paths\n        for(List<String> path : paths)\n            if(isValid(root, path)) // Check if the path is not duplicate\n                ans.add(path);\n        return ans;\n    }\n    void addPath(Node root, List<String> path)\n    {\n        // Simple Trie insertion\n        for(String s : path)\n        {\n            if(!root.children.containsKey(s))\n                root.children.put(s, new Node(s));\n            root = root.children.get(s);\n        }\n    }\n    StringBuilder buildHash(Node root)\n    {\n        // encode the subtree root as: "root(child1)(child2)(child3)..." but recursively\n        StringBuilder ret = new StringBuilder(root.s); // To return\n        for(String s : root.children.keySet()) // Recursively solve for all children\n            ret = ret.append("(").append(buildHash(root.children.get(s))).append(")"); // "root(child1)(child2)(child3)..."\n        String x = new String(new StringBuilder("#").append(ret.substring(root.s.length()))); // replace first value by # beacuse a->b and c->b are duplicate folders (see Example 1)\n        \n        // x has 1st value replaced by # but ret has nothing replaced\n        \n        if(ret.length()==root.s.length())               ///  Fixed a bug here\n            x = root.s;                                 ///  Leaf node frequency should not be increased\n        else                                            ///  See Example 5, Withot this fix, path a->z and b->z got removed\n            freq.put(x, freq.getOrDefault(x, 0) + 1);   // Increment frequency of current subtree\n        root.encoded = x;                               // Store the encoded subtree in root node\n        return ret;  // return string of the form "root(child1)(child2)(child3)..."\n    }\n    boolean isValid(Node root, List<String> path)\n    {\n        for(int i = 0; i < path.size(); i++)\n        {\n            root = root.children.get(path.get(i));\n            if(freq.getOrDefault(root.encoded, 1) != 1) // There are multiple occurences of this subtree so return invalid path\n                return false;\n        }\n        return true;\n    }\n}\n```
[]