DSA problem
Remove Sub-Folders from the Filesystem
Given a list of folder paths folder, remove all sub-folders in those paths and return the folders in any order. A folder b is a sub-folder of folder a if and only if a is a prefix of b AND that prefix is followed by a / in b. For example, /a/b is a sub-folder of /a, but /a/b is NOT a sub-folder of /a/b/c even though /a/b is a prefix of /a/b/c (the relationship is reversed there).
The trailing-slash requirement matters: /abc is not a sub-folder of /ab because the prefix /ab is followed by c instead of /. A correct algorithm must respect this boundary explicitly.
The most elegant solution sorts the folders lexicographically. After sorting, any sub-folder is guaranteed to appear immediately after its parent (since the parent string is a prefix of the sub-folder string), so a single pass can keep only the top-level folders. Maintain a list of accepted folders; for each candidate, accept it unless it begins with lastAccepted + '/'.
This runs in O(N log N * L) time for sorting where N is the number of folders and L is the average length, plus O(N * L) for the linear scan. Space is O(N * L) for the result. An alternative trie approach builds a tree of path segments and accepts a folder only at the first node it reaches with an isEnd flag along its path; that yields the same asymptotic behavior but with higher constants and more memory.
Examples
folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]["/a","/c/d","/c/f"]folder = ["/a","/a/b/c","/a/b/d"]["/a"]folder = ["/a/b/c","/a/b/ca","/a/b/d"]["/a/b/c","/a/b/ca","/a/b/d"]Constraints
- 1 <= folder.length <= 4 * 10^4
- 2 <= folder[i].length <= 100
- folder[i] contains only lowercase letters and '/'.
- folder[i] always starts with the character '/'.
- Each folder name is unique.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.