Remove Subfolders in FIle System

XXX. Remove Subfolders

String

Sorting

HashSet

Problem Statement:

Given an array of folders, remove all subfolders. A folder is a subfolder of another folder if it's path is a prefix of the other folder's path.

• All folders start with '/'
• No folder is prefix of another folder's name
• Return remaining folders in any order

Implementation:

Java Solution:

public List removeSubfolders(String[] folder) {
    // Sort by length for processing shortest paths first
    Arrays.sort(folder, Comparator.comparing(s -> s.length()));
    Set seen = new HashSet<>();
    
    outer:
    for (String f : folder) {
        // Check each possible parent folder path
        for (int i = 2; i < f.length(); ++i) {
            if (f.charAt(i) == '/' && seen.contains(f.substring(0, i)))
                continue outer;          // Skip if parent folder exists
        }
        seen.add(f);                    // Add if no parent found
    }
    
    return new ArrayList<>(seen);
}
                

Python Solution:

def removeSubfolders(self, folder: List[str]) -> List[str]:
    # Sort by length for processing shortest paths first
    folder.sort(key=len)
    seen = set()
    
    for f in folder:
        # Check each possible parent folder path
        parent_found = False
        for i in range(2, len(f)):
            if f[i] == '/' and f[:i] in seen:
                parent_found = True
                break
        if not parent_found:
            seen.add(f)                 # Add if no parent found
    
    return list(seen)
                

C++ Solution:

vector removeSubfolders(vector& folder) {
    // Sort by length for processing shortest paths first
    sort(folder.begin(), folder.end(), 
         [](const string& a, const string& b) { return a.length() < b.length(); });
    
    unordered_set seen;
    
    for (const string& f : folder) {
        bool is_subfolder = false;
        // Check each possible parent folder path
        for (int i = 2; i < f.length(); ++i) {
            if (f[i] == '/' && seen.count(f.substr(0, i))) {
                is_subfolder = true;
                break;
            }
        }
        if (!is_subfolder)
            seen.insert(f);             // Add if no parent found
    }
    
    return vector(seen.begin(), seen.end());
}
                

Complexity:

Time Complexity: O(N * L * logN), where N is number of folders and L is average folder length
Space Complexity: O(N * L) for storing folders

Explanation:

• **Sorting Strategy**:
  • Sort by length to process shortest paths first
  • Ensures parents are processed before children
  • Simplifies subfolder detection
• **Path Processing**:
  • Check each '/' position for potential parent
  • Extract substring up to '/' as possible parent
  • Skip folder if parent exists in set
• **Implementation Notes**:
  • Use HashSet for O(1) lookups
  • Label-based continue in Java
  • Different string handling in each language