0569MediumArrayStringDepth-First SearchTrie

Backup Roots Only

Tracked in this browser only

Trains the technique from

LeetCode 1233Remove Sub-Folders from the Filesystem

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A backup tool is handed a list of directory paths in folder, in no particular order. Each path starts with / and its directory names are separated by /, for example /store/rack/shelf names the directory shelf inside rack inside store.

A path is nested when another path in the list names one of its ancestor directories: /store/rack/shelf is nested when /store or /store/rack is also listed. Matching is by whole directory names, so /store/rackham is not nested inside /store/rack even though the text of one begins with the text of the other.

Backing up a directory covers everything under it, so the tool drops every nested path. Return the paths that survive, sorted in ascending lexicographic order by their characters.

Examples

Example 1

Input: folder = ["/store/rack", "/store/rackham", "/store/rack/shelf", "/store"]
Output: ["/store"]

`/store` is listed, so `/store/rack` and `/store/rackham` are both nested inside it, and `/store/rack/shelf` is nested too. Only `/store` survives.

Example 2

Input: folder = ["/a/b", "/a/bc"]
Output: ["/a/b", "/a/bc"]

Neither path names an ancestor of the other: `b` and `bc` are different directory names inside `/a`, and `/a` itself is not in the list.

Example 3

Input: folder = ["/p", "/p/q/r"]
Output: ["/p"]

`/p` is an ancestor of `/p/q/r`, even though the directory `/p/q` between them is not listed, so the deeper path is dropped.

Constraints

1 <= folder.length <= 4 * 10^4
2 <= folder[i].length <= 100
folder[i] consists of lowercase English letters and '/'.
folder[i] starts with '/' and does not end with '/'.
All paths in folder are distinct.
The result is sorted in ascending lexicographic order.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def remove_subfolders(folder: list[str]) -> list[str]:

Java

public List<String> removeSubfolders(String[] folder)

The intended approach

Time O(n * L log n), dominated by sorting n paths of length up to L.Space O(n * L) for the sorted copy and the returned list.

Sort the paths as plain strings. In that order any ancestor of a path appears before it, and every path nested under a given survivor forms an unbroken run immediately after it, so one pass suffices: keep a path when it is not nested under the most recent survivor, otherwise skip it. The test appends a separator to the survivor before comparing, which keeps a sibling whose name merely starts with the survivor's last name from being dropped. The kept list is already in ascending order, which is the order required.

Pythonentry point: remove_subfolders

def remove_subfolders(folder):
    # O(n * L log n) time, O(n * L) space: in ascending order a directory always
    # comes before anything nested inside it, so one pass keeping the most recent
    # survivor is enough. The separator in the comparison is what stops a name
    # that merely starts with the survivor's text from being swallowed.
    order = sorted(folder)
    kept = []
    for path in order:
        if kept and path.startswith(kept[-1] + "/"):
            continue
        kept.append(path)
    return kept

The obvious version

Split every path into its directory names. For each path, compare it against every other path and drop it when some shorter name list matches its opening names exactly. Sort what is left.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_remove_subfolders(folder):
    parts = [p.split("/") for p in folder]
    out = []
    for i in range(len(folder)):
        inside = False
        for j in range(len(folder)):
            if i == j:
                continue
            a = parts[j]
            b = parts[i]
            if len(a) >= len(b):
                continue
            match = True
            for k in range(len(a)):
                if a[k] != b[k]:
                    match = False
                    break
            if match:
                inside = True
                break
        if not inside:
            out.append(folder[i])
    return sorted(out)

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in