Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Two folders are duplicates when their nonempty child-folder structures match, including descendant names, even if the folders themselves have different names. A canonical serialization of each subtree lets matching structures share a key. Deletions must be decided from the original tree, not repeated after removing folders.

Approach

Insert sorted paths into a trie, giving child traversal a consistent name order. Serialize each nonleaf node by concatenating every child name with its parenthesized subtree serialization, and group nodes by this key. Leaves return an empty serialization but are not grouped as duplicates. Mark every node belonging to a repeated nonempty key. Finally traverse the trie, skipping marked nodes and their entire subtrees, and collect surviving paths. Do not recompute duplicate groups after marking: the task requires one simultaneous deletion pass.

class Trie:
    def __init__(self):
        # self.children = {}
        self.children = defaultdict(Trie)
        self.delete = False

    def add(self, word):
        curr = self

        for c in word:
            # if c in curr.children: curr = curr.children[c]
            # else: curr.children[c] = Trie()
            curr = curr.children[c]

class Solution:
    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:
        root = Trie()

        for path in sorted(paths):
            root.add(path)

        def serialize(t):
            if not t.children:
                return ""

            s = []

            for folder, child in t.children.items():
                s.append(folder + '(' + serialize(child) + ')')

            key = "".join(s)
            seen[key].append(t)
            return key

        seen = defaultdict(list)
        serialize(root)

        for nodes in seen.values():
            if len(nodes) >= 2:
                for node in nodes:
                    node.delete = True

        def dfs(root, path):
            for folder, child in root.children.items():
                if not child.delete:
                    curr = path + [folder]
                    res.append(curr)
                    dfs(child, curr)

        res = []
        dfs(root, [])
        return res

Complexity analysis

Let P be the path count, D the maximum depth, L the maximum folder-name length (at most 10), A the total input path-component count, N the trie-node count, C the total character length of all subtree serializations materialized, and Q the total number of components in returned paths. With expected hash-map access, time is O(PDL log(P + 1) + AL + N + C + Q): sorting compares names, trie insertion processes input components, serialization copies/hashes descendant names, and collection copies each returned path. C need not be linear in N because descendant text is repeated in ancestor keys. Auxiliary space excluding output is O(P + N + C + D), including sorting references, trie/groups, serialization buffers and recursion. Output uses O(Q) references; path copies share folder-name strings rather than copying their characters.