〽️ Beginner-Friendly Guide: "Remove Sub-Folders from Filesystem" – LeetCode 1233 (C++ | Python | JavaScript)

#programming #cpp #javascript #pytho

Managing filesystem hierarchies is a fundamental operation across systems. In this problem, we are given a list of folder paths and need to remove sub-folders, retaining only the top-level directories. This challenge not only helps in understanding path manipulation but also teaches efficient sorting and string matching techniques.

🧠 Problem Summary

Input: A list of folder paths represented as strings, where each folder starts with '/' followed by lowercase letters.
Goal: Remove any folder that is a sub-folder of another.
Constraint: A sub-folder is defined if its path starts with another folder's path, immediately followed by a '/'.

Example:

Input: ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]

💡 Intuition

Sorting: By sorting all folder paths lexicographically, parent folders naturally appear before their sub-folders.
Tracking: Keep track of the previous folder added to the answer.
Checking Sub-folder: For each folder, check if it starts with the prev folder plus '/'. If so, it's a sub-folder and should be skipped.
Otherwise: Add the current folder to the answer and update prev.

🛠️ C++ Code

#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        vector<string> ans;
        string prev;

        sort(folder.begin(), folder.end());

        for (const string& f : folder) {
            if (!prev.empty() && f.find(prev) == 0 && f[prev.length()] == '/')
                continue;
            ans.push_back(f);
            prev = f;
        }

        return ans;
    }
};

🐍 Python Code

from typing import List

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()
        ans = []
        prev = ""

        for f in folder:
            if prev and f.startswith(prev) and f[len(prev)] == '/':
                continue
            ans.append(f)
            prev = f

        return ans

💻 JavaScript Code

var removeSubfolders = function(folder) {
    folder.sort();
    const ans = [];
    let prev = "";

    for (const f of folder) {
        if (prev && f.startsWith(prev) && f[prev.length] === '/') {
            continue;
        }
        ans.push(f);
        prev = f;
    }

    return ans;
};

📝 Key Takeaways

Sorting: Sorting lexicographically is the core trick that ensures parent directories appear before sub-folders.
Prefix Check: f.find(prev) == 0 and f[prev.length()] == '/' efficiently checks for the sub-folder condition.
Performance: This approach is efficient, running in O(n log n) time due to sorting, where n is the number of folders.

✅ Final Thoughts

This problem is a great example of how simple sorting combined with careful prefix checking can solve seemingly complex hierarchical challenges. The technique is broadly useful in handling path-based or string-prefix problems across applications.