💥💥Beats 100% on runtime and memory [EXPLAINED]
\n\n\n# Intuition\nFind duplicate folder structures in a file system, where two folders are considered identical if they have the same set of subfolders and arr
![image.png](https://assets.leetcode.com/users/images/9e27a52e-741f-4fee-8cd4-19387b5f118f_1729420144.4752522.png)\n\n\n# Intuition\nFind duplicate folder structures in a file system, where two folders are considered identical if they have the same set of subfolders and arrangement, regardless of their position in the hierarchy.\n\n# Approach\nWe construct a tree representation of the folders, serialize each subtree while masking the current node\'s value to identify duplicates, and then remove any folders that belong to duplicate structures before returning the remaining unique folders.\n\n# Complexity\n- Time complexity:\n O(N log N) due to sorting folder names for serialization, where N is the total number of folders.\n\n- Space complexity:\nO(N) for storing the folder tree and duplicate mapping.\n\n# Code\n```typescript []\nclass Node {\n    val: string | null;\n    parent: Node | null;\n    children: { [key: string]: Node };\n\n    constructor(val: string | null, parent: Node | null) {\n        this.val = val;\n        this.parent = parent;\n        this.children = {};\n    }\n}\n\n/**\n * Deletes duplicate folders in the file system.\n * \n * @param paths - The input array representing paths to folders.\n * @return The resulting paths after deleting duplicate folders.\n */\nfunction deleteDuplicateFolder(paths: string[][]): string[][] {\n    // Step 1: Construct the folder tree from the paths\n    const root = new Node(null, null);\n    for (const path of paths) {\n        let current = root;\n        for (const folder of path) {\n            // Create child node if it doesn\'t exist\n            if (!current.children[folder]) {\n                current.children[folder] = new Node(folder, current);\n            }\n            current = current.children[folder];\n        }\n    }\n\n    // Step 2: Identify duplicate folder structures\n    const subTreeMap: { [key: string]: Node[] } = {};\n\n    function serializeSubTree(node: Node): string {\n        if (Object.keys(node.children).length === 0) {\n            return node.val as string; // Leaf node\n        }\n\n        let serialized = `${node.val},`;\n        // Sort children to ensure consistent traversal order\n        Object.keys(node.children).sort().forEach((key) => {\n            serialized += serializeSubTree(node.children[key]) + ",";\n        });\n\n        // Create a unique signature for the subtree, masking the current node\'s value\n        const maskedSignature = serialized.replace(`${node.val},`, \'*,\');\n        if (!subTreeMap[maskedSignature]) {\n            subTreeMap[maskedSignature] = [];\n        }\n        subTreeMap[maskedSignature].push(node); // Store the node reference\n        return serialized;\n    }\n\n    serializeSubTree(root);\n\n    // Step 3: Remove duplicate folders\n    for (const nodes of Object.values(subTreeMap)) {\n        if (nodes.length > 1) {\n            nodes.forEach(node => {\n                if (node.parent) {\n                    delete node.parent.children[node.val as string]; // Remove from parent\n                }\n            });\n        }\n    }\n\n    // Step 4: Generate the final list of remaining folder paths\n    const result: string[][] = [];\n\n    function generatePaths(node: Node, path: string[]) {\n        if (node.val) {\n            path.push(node.val);\n            result.push([...path]); // Store the current path\n        }\n        Object.keys(node.children).forEach(key => {\n            generatePaths(node.children[key], path); // Recur for children\n        });\n        path.pop(); // Backtrack to explore other paths\n    }\n\n    generatePaths(root, []);\n    return result;\n}\n\n\n```
['TypeScript']