Remove Sub-Folders from Filesystem

Given an array of directory strings, return only the parent directories.

Sort and Remove O(n log n)

After sorting, directories that might be parent-child pairs will appear together, with the parent always coming first. We can remove duplicates by checking if string prefixes match.

This turns a hierarchical problem into a linear one, avoiding space used for building tree structures.

class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        sort(folder.begin(), folder.end());
        vector<string> res;
        res.push_back(folder[0]);
        for(int i=1;i<folder.size();++i) {
            string s = res.back()+"/";
            if (folder[i].substr(0, s.size())!=s) {
                res.push_back(folder[i]);
            }
        }
        return res;
    }
};

#string