Python 3: TC O(N log(N)) SC O(N): SHA256 Substructure Hashes
Intuition\n\nThis is a pretty nasty problem IMO.\n\nThe key I think is to know either\n substructure hashes exist\n or that you can probably just serialize the 
# Intuition\n\nThis is a pretty nasty problem IMO.\n\nThe key I think is to know either\n* substructure hashes exist\n* or that you can probably just serialize the substructures exactly as I saw another submission do and hash those without TLE\n\n## Brute Force, Always Correct\n\nMost solutions to this problem do the following:\n* have a way to serialize (some call it "hashing," but they\'re actually serializing the tree) to a string\n  * e.g. [DBabichev](https://leetcode.com/problems/delete-duplicate-folders-in-system/solutions/1361419/python-serialize-subtrees-complexity-analysis-explained/) uses something like `a()b(c(),d())...z()` to serialize a directory with children `a/`, `b/c/`, `b/d/`, etc.\n* traverse the tree, building up the serialized string from the bottom up and adding it to a hashmap\n\nThen any node whose serialized substructure shows up 2+ times in the hashmap is NOT unique and should thus be deleted.\n\n## Approximate, Faster\n\nBuliding hashes from the bottom up becomes quadratic in tree depth because you keep adding a prefix to a long suffix at each level of the tree.\n\nIt\'s fast enough I guess given the bounds on the problem, but not as fast as it could be.\n\nA faster solution is to **hash substructures intead of serializing them**.\n\nWe\'re basically doing a Rabin-Karp approach to finding duplicates in the tree. Each subtree has a hash, and with high probability, if a hash appears 2+ times then we have a duplicate substructure.\n\n### First Attempt: foo * 27 + offset + 1\n\nMy first try was to do my own hashing.\n\nIt failed because of conflicts.\n\nThe tricky thing is that we need a LOT of entropy, each configuration of the tree needs to produce a hash that\'s very different. Otherwise you end up with cases where two different trees have the same hash and causes an error.\n\nMy attempts at a basic *27 + offset + 1 rolling-hash-like thing just weren\'t cutting it. Not enough bits with all the short directory names.\n\n### Second Attempt: Cryptographic Hash\n\nFortunately there\'s a way of getting order-dependent, arity-dependent hashes with cryptographic strength, i.e. it\'s very hard to get duplicate hashes even if you try: cryptographic hashes.\n\nThe SHA family of hashes, really called "digests" because they "digest" a ton of data and produce one binary summary, have the cryptographic strength property.\n\nSo my new algorithm to generate the hash for each node is to\n* sort the children by directory name, so we add things to the hash in a canonical order. Otherwise if we process identical substructures but in a different traversal order we\'d get a different hash (false negative)\n* then\n  * add the child name to the digest\n  * add the child\'s digest to the current digest\n* then return the digest as we ascend the tree so the parent can make its own digest\n\nThe result is a cryptographic strength hash for the structure with a very VERY low chance of hash collisions.\n\nSeriously. You\'d have to try REALLY REALLY hard to find identical hashes.\n\nYour best best would be a "birthday attack," where you exploit the [Birthday Paradox](https://en.wikipedia.org/wiki/Birthday_problem).\n\nSHA256 has a LOT of bits and therefore even very large inputs will very rarely have a collision.\n\n# Complexity\n- Time complexity: `O(N**2)`. The worst case is where the tree is very shallow so we have to sort `O(N)` children. The SHA256 digest does `O(1)` work per child for each node (albeit a hefty `O(1)`)\n  - meanwhile, for `O(N)` levels deep, we would append a length-1 path to the output, and length-2, and length-3, etc. `O(N)` paths of length `O(N)` -> `O(N**2)` \n\n- Space complexity: `O(N)`, we use at most `O(N)` stack memory for a very deep tree, and each path has a hash\n\n# Comments\n\nSubstructure hashes show up when trying to identify isomorphic graphs.\n\nFinding all of them exactly is NP complete, but with hashes you can get a faster algorithm with high probability of no collisions.\n\nYou can also always verify the collisions too to ensure correctness.\n\n# Code\n```\nfrom hashlib import sha256\n\nclass Solution:\n    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:\n        # 2D array paths, paths[i] is for example ["a", "b", "c"] representing /a/b/c/\n        #\n        # two folders are identical if they have the same nonempty set of subfolders with the same structure\n\n        # they need not be at the same level, ugh\n\n        # then delete all the duplicates\n        \n        # following paths builds up a directory trie\n        #\n        # nodes in that trie that are identical to another node in the trie should both be deleted\n\n        # we delete in a single round\n\n        # up to\n        #   2e4 paths\n        #   5e2 entries per path\n        #   10 chars per path entry\n        #   2e5 chars total across all paths\n\n        # all chars are lowercase\n        \n        # no two paths lead to the same place\n\n        # building the directory trie is easy\n\n        # identifying identical subtrees is hard, I think NP-hard if you insist on a deterministic 100% algo\n        #\n        # but we can use a Merkle tree approach, structure hash, etc. to help us\n        # suppose the current node in the trie has a subfolder structure hash of x\n        # if there\'s another subtrie with the same hash, mark both for deletion\n\n        # subtrie hash: need to combine in an order dependent way, or in a canonical order\n\n        # suppose we hash names, somehow\n        # then the resulting hash can be an xor of names, or we can sort names and do a more RK-like rolling hash\n\n        # when we combine hashes we\'ll take priorHash*26+25 at most, so maxHash = maxInt-25 ) // 26\n        BIG = (0x7FFFFFFFFFFFFFFF - 26)//27\n\n        # if we have a child via name foo with structure hash x, then\n        #       mix x with the name hash I guess via the same procedure\n        #\n        # and then do xor across children?\n\n        class DirNode:\n            def __init__(self):\n                self.children = {} # dir name -> child node\n                self.hash = 0 # to be filled in later\n\n            def add(self, name: str) -> \'DirNode\':\n                if name not in self.children:\n                    self.children[name] = DirNode()\n\n                return self.children[name]\n\n        root = DirNode()\n\n        for path in paths:\n            curr = root\n            for d in path:\n                curr = curr.add(d)\n\n        oa = ord(\'a\')\n        hash_freqs = defaultdict(int)\n        def setHashes(node):\n            # hash of node is\n            #    > take each child trie, get its structure hash, mix with the name\n            #    > then xor over all children\n\n            digester = sha256() # FIX: bring out the big guns\n            for dirname, child in sorted(node.children.items()):\n                child_hash = setHashes(child)\n\n                digester.update(dirname.encode())\n                digester.update(child_hash)\n\n\n            digest = digester.digest()\n            hash_freqs[digest] += 1\n            node.hash = digest\n            return digest\n\n        setHashes(root)\n\n        ans = []\n        curr_path = []\n        def findPaths(node) -> None:\n\n            # FIX: only delete if it has the same nonempty set of children and substructure, so don\'t delete leaves b/c set is empty\n            if hash_freqs[node.hash] == 1 or not node.children:\n                if curr_path:\n                    ans.append(curr_path[:]) # unique structure hash: this dir should NOT be deleted, append root-to-here path to answer\n\n                for dirname, child in node.children.items():\n                    curr_path.append(dirname)\n                    findPaths(child)\n                    curr_path.pop()\n\n            # else: this is deleted, so this substructure matches another substructure, so\n            # the children are all duplicates too\n\n        findPaths(root)\n\n        return ans\n```
['Python3']