Python Hashmap
Let N, M, and K be the number of folders, sum(len(paths[i])), and the maximum length of folder name respectively.\n1. Make a tree structure from \'paths\'\n    
Let N, M, and K be the number of folders, sum(len(paths[i])), and the maximum length of folder name respectively.\n1. Make a tree structure from \'paths\'\n    time complexity: O(M)\n\tspace compexity O(NK)\n```\nclass Node:\n    def __init__(self, val, parent=None, children=None):\n        self.val = val\n        self.children = {}\n        self.group = -1\n        self.key = None \n\t\t\nclass Solution:\n    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:\n\t\troot = Node(\'/\')\n\t\tfor path in paths:\n\t\t\tnode = root\n\t\t\tfor name in path:\n\t\t\t\tif name not in node.children:\n\t\t\t\t\tnode.children[name] = Node(name)\n\t\t\t\tnode = node.children[name]\n```\n\n2. To group and count \'identical\' subtrees, use a hashmap. Instead of using the serialized string of each subtree as the key, use tuples of the children\'s group number and children\'s name for the key. Only for the leaf nodes use their name as the key.\n    time complexity: O(N log(N)) for sort and O(NK) for making and using keys\n\t\n```\n\t\tumap = dict() \n\t\t\n        def dfs(root):\n            if not root.children:\n                root.key = root.val\n            else:\n                for child in root.children.values():\n                    dfs(child)\n                root.key = tuple(sorted((child.group, child.val) for child in root.children.values()))\n            \n            nonlocal umap\n            if root.key not in umap:\n                umap[root.key] = [len(umap), 1]\n            else:\n                umap[root.key][1] += 1\n            root.group = umap[root.key][0]\n        \n        dfs(root)\n```\n\n3. Read valid paths by excluding duplicate nodes that are not leaves.\n    time complexity: same as in part 2\n```\n        def readPaths(root, cand, res):\n            nonlocal umap\n            for child in root.children.values():\n                if umap[child.key][1] == 1 or type(child.key) == str:\n                    cand.append(child.val)\n                    res.append(list(cand))\n                    readPaths(child, cand, res)\n                    cand.pop()\n                    \n        res = []\n        readPaths(root, [], res)\n        return res\n```\n\nOverall time complexity: O(M + N log(N) + NK)\nOverall space complexity: O(NK)
[]