Python solution + explanation
Intuition\n1. Use Trie for Optimal Storage\n2. Serialize Trie Nodes\n3. Detect and Mark Duplicates\n4. Construct Result Paths\n\n# Approach\n1. Use Trie for Opt
# Intuition\n1. Use Trie for Optimal Storage\n2. Serialize Trie Nodes\n3. Detect and Mark Duplicates\n4. Construct Result Paths\n\n# Approach\n1. Use Trie for Optimal Storage:\n**Reason**: A Trie efficiently stores hierarchical paths, where each node represents a directory and paths share common prefixes.\n**Alternative**: While a general tree or graph could also represent the paths, Tries are efficient for prefix-based operations and hierarchical data.\n\n1. Serialize Trie Nodes:\n**HashKey**: Serialize each Trie node into a unique string representation. The format used is "<parent_name>(serialize(child_subtrie))".\n**Consistency**: Ensure children are sorted lexicographically during serialization to maintain consistency.\n**Storage**: Store serialized nodes in a `children_hash` HashMap. Each unique serialized string points to a list of parent nodes.\n\n1. Detect and Mark Duplicates:\nIterate over the `children_hash` and mark nodes for deletion if their serialized subtree appears more than once (i.e., if the list of parents has more than one node).\n\n1. Construct Result Paths:\n**Backtracking**: For each non-deleted node, append the folder name to the current path and add it to the results list.\n\n# Complexity\n- Time complexity: `O(N*Llog(L))`\n\nInsertion: `O(L)`, where `L` is the average length of the paths.\nSerialization: `O(N*Llog(L))`\n`N` - the number of nodes\n`L` - max(length of a path).\n`L*log(L)` - sorting the children for each node during serialization \n\n- Space complexity: `O(N+L)`\n`N` - the number of nodes\n`O(L)` - maximum depth of the recursive call stack during serialization\n\n# Code\n```python3\nclass TrieNode():\n    def __init__(self):\n        self.children = {}\n        self.to_delete = False\n\nclass Trie:\n    def __init__(self):\n        self.root = TrieNode()\n        self.children_hash = defaultdict(list)\n\n    def insert_paths(self, paths: List[List[str]]):\n        for path in paths:\n            cur = self.root\n            for folder in path:\n                if folder not in cur.children:\n                    cur.children[folder] = TrieNode()\n                cur = cur.children[folder]\n    \n    def serialise_children(self, node):\n        hash_key = []\n        for name, child in sorted(node.children.items()):\n            hash_key.append(f"{name}({self.serialise_children(child)})")\n        \n        hash_key_str = "".join(hash_key)\n        if hash_key_str:\n            self.children_hash[hash_key_str].append(node)\n        return hash_key_str\n        \n    def mark_duplicates(self):\n        for hash_key in self.children_hash:\n            if len(self.children_hash[hash_key]) > 1:\n                for node in self.children_hash[hash_key]:\n                    node.to_delete = True\n\n    def _construct_result_path(self, node, path, result):\n        for ch, child in node.children.items():\n            if not child.to_delete:\n                path.append(ch)\n                result.append(path[:])\n                self._construct_result_path(child, path, result)\n                path.pop()\n\n    def get_folders_without_duplicates(self):\n        result = []\n        self._construct_result_path(self.root, [], result)\n        return result\n\nclass Solution:\n    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:\n        trie = Trie()\n        trie.insert_paths(paths)\n        trie.serialise_children(trie.root)\n        trie.mark_duplicates()\n        result = trie.get_folders_without_duplicates()\n        return result\n```
['Hash Table', 'Backtracking', 'Trie', 'Python3']