O(N) time solution (for dedup), not O(N^2)
Intuition\n\nAssumptions:\nK = sum(paths[i].length)\nN = Number of nodes in folder structure\nW = Length of folder name\nP = paths.length\nD = max(paths[i].leng
# Intuition\n\nAssumptions:\nK = sum(paths[i].length)\nN = Number of nodes in folder structure\nW = Length of folder name\nP = paths.length\nD = max(paths[i].length)\n\nWe run dedup operation to find common subtrees in the folder structure. Dedup will rewire the references to child nodes to point to the same common subtrees. This allows us to improve the time complexity of dedup to O(N W) (as opposed to O(N^2 W)) where N is the number of nodes in the original folder structure (pre-dedup) and W is length of folder name. \n\n# Approach\n1) Build the folder tree from the given paths. Takes O(K W) time.\n2) Run dedup. If a subtree is common across different parts of the larger tree make sure that same Node object (representing that subtree) is referenced across the different parts of the larger tree. Takes O(N W) time.\n3) Group nodes which have common substructure. Takes O(N W) time.\n4) If a group has 2 or more nodes, mark each of those nodes for removal. Takes O (N) time.\n5) Build final output, ignoring nodes marked for removal. O(N W + D^2 P)\n\n# Complexity\n- Time complexity:\nO (K W + D^2 P)\n\n- Space complexity:\nO (N W)\n\n# Code\n```\nclass Solution {\n    \n    class Node {\n        Integer hash;\n        boolean marked;\n        String name;\n        HashMap<String,Node> children;\n        Node(String name){\n            this.name = name;\n            children = new HashMap<>();\n        }\n        public int hashCode(){\n            if(hash==null) hash = children.hashCode();\n            return hash;\n        }\n        public boolean equals(Object o){\n            if (this == o) return true;\n            if (o == null) return false;\n            if (this.getClass() != o.getClass()) return false;\n            Node other = (Node) o;\n            if(this.children.size()!=other.children.size()) return false;\n            for(String ch:this.children.keySet()){ \n                //Only check shallow equality of Node objects (assumption is that they have already been deduped). \n                //Checking deep equality would have caused dedup to take O(N^2 W) time.\n                if(this.children.get(ch)!=other.children.get(ch)) return false;\n            }\n            return true;\n        }\n    }\n    \n    HashMap<String,HashMap<Node,Node>> dedupMap;\n    \n    Node dedup(Node node){\n        for(String ch:node.children.keySet()){\n            Node chNode = dedup(node.children.get(ch));\n            node.children.put(ch,chNode);\n        }\n        HashMap<Node,Node> g = dedupMap.get(node.name);\n        if(g==null){\n            g = new HashMap<>();\n            g.put(node,node);\n            dedupMap.put(node.name,g);\n            return node;\n        } else {\n            Node dup = g.get(node);\n            if(dup==null){\n                g.put(node,node);\n                return node;\n            } else {\n                return dup;\n            }\n        }\n    }\n    \n    HashMap<Node,List<Node>> groups;\n    \n    void createGroups(Node node){\n        if(!groups.containsKey(node)){\n            groups.put(node, new ArrayList<>());\n        }\n        groups.get(node).add(node);\n        for(String ch:node.children.keySet()){\n            createGroups(node.children.get(ch));\n        }\n    }\n    \n    List<List<String>> ans;\n    \n    void buildAns(Node node, List<String> path){\n        if(node.marked && node.children.size()>0) return;\n        path.add(node.name);\n        ans.add(new ArrayList<>(path));\n        for(String ch:node.children.keySet()){\n            buildAns(node.children.get(ch),path);\n        }\n        path.remove(path.size()-1);\n    }\n    \n    public List<List<String>> deleteDuplicateFolder(List<List<String>> paths) {\n        Node root = new Node("/");\n        for(List<String> path:paths){\n            Node cur = root;\n            for(String fold:path){\n                if(!cur.children.containsKey(fold)){\n                    cur.children.put(fold,new Node(fold));\n                }\n                cur=cur.children.get(fold);\n            }\n        }\n        dedupMap = new HashMap<>();\n        root = dedup(root);\n        groups = new HashMap<>();\n        createGroups(root);\n        for(Map.Entry<Node,List<Node>> entry:groups.entrySet()){\n            if(entry.getValue().size()>1){\n                for(Node node:entry.getValue()) node.marked=true;\n            }\n        }\n        ans = new ArrayList<>();\n        for(String ch:root.children.keySet()){\n            buildAns(root.children.get(ch), new ArrayList<>());\n        }\n        return ans;\n    }\n}\n```
['Java']