Problem Breakdown
We are given an array of file system paths (strings starting with /). The goal is to remove any path that is strictly inside another path in the list (a sub-folder). A folder A is a sub-folder of B if and only if B appears as a prefix followed by exactly one slash (/) before the rest of A. For example, /a/b/c is a sub-folder of /a, but not of /ab.
Inputs:
- A list of strings
folder. Each string starts with/. - Constraints: , length . Unique names.
Outputs:
- A filtered list containing only the “root” folders (parents), excluding their descendants. Order does not matter for output but sorting helps processing logic.
Intuition
A brute-force approach comparing every pair of folders would be , which will exceed time limits given .
Key Insight: If we sort the list lexicographically (ASCII order), parent paths always appear before their children. For instance, /a comes before /a/b, and /a/b comes before /c/d.
Once a folder is added to our result set (meaning it’s not inside any previously kept folder in the sorted sequence), all subsequent folders that start with kept_folder + '/' must be its sub-folders. Any folder that does not match this prefix pattern belongs to a different branch or is unrelated, so we keep it as a new root for our result set and update our reference point.
Approach
- Sort the input list lexicographically using
folder.sort(). This groups parents before children (e.g.,/athen/a/b). - Initialize an empty
resultlist to store valid folders. - Iterate through each folder in the sorted list:
- If the result list is empty, add the current folder immediately.
- Otherwise, check if the current folder starts with the string of the last added folder followed by a slash (
/). - If it does match (e.g., last was
/a, current is/ab-> No; last was/a, current is/abc-> Yes), skip it as it’s a sub-folder. Note: The check must bestartswith(last + "/"). This distinguishes between/aand/ab. - If it does not match, add the folder to
result. It becomes the new reference for checking subsequent folders in this branch of the tree.
- Return
result.
Complexity Analysis
- Time: where is number of folders and is max string length (for sorting). The iteration takes . Sorting dominates, fitting well within time limits for 40k items.
- Space: Python’s
list.sort()uses Timsort which requires auxiliary space proportional to the input size in worst-case scenarios (), though often optimized. Excluding this and output storage, logic is . The result list takes where K is number of kept folders (worst case ).
Solution
from typing import List
def remove_sub_folders(folder: List[str]) -> List[str]:
# Sort lexicographically so parents appear before children
folder.sort()
result = []
for f in folder:
if not result or not (f.startswith(result[-1] + "/")):
result.append(f)
return result
# Example usage / verification logic inside thought process,
# but function is clean and idiomatic.
Edge Cases Handled
- Single Folder: Loop runs once, condition
not resulttriggers immediately; returns list with that folder. - Non-Matching Prefixes (e.g.,
/a/bvs/ab/c): String sort places them in order (/a...then/b...). The checkstartswith(result[-1] + "/")ensures strict path hierarchy matching, preventing false positives like treating/abas a parent of/abc. - Deeply Nested Structures: Sorting guarantees that if we keep the root (e.g.,
/root/child/grandchild), any subsequent folder starting with...grandchild/is skipped. If an unrelated path appears later, it won’t match the prefix and gets added correctly.