Given a list of folders folder, return the folders after removing all sub-folders in those folders. You may return the answer in any order.

If a folder[i] is located within another folder[j], it is called a sub-folder of it.

The format of a path is one or more concatenated strings of the form: '/' followed by one or more lowercase English letters.

For example, "/leetcode" and "/leetcode/problems" are valid paths while an empty string and "/" are not.

Examples

Example 1:

Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]
Explanation: Folders "/a/b" is a subfolder of "/a" and "/c/d/e" is inside of folder "/c/d" in our filesystem.

Example 2:

Input: folder = ["/a","/a/b/c","/a/b/d"]
Output: ["/a"]
Explanation: Folders "/a/b/c" and "/a/b/d" will be removed because they are subfolders of "/a".

Example 3:

Input: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
Output: ["/a/b/c","/a/b/ca","/a/b/d"]
Explanation: None of the folders are subfolders of another folder.

Constraints

  • 1 <= folder.length <= 4 * 10^4
  • 2 <= folder[i].length <= 100
  • folder[i] contains only lowercase letters and '/'
  • folder[i] always starts with '/'
  • Each folder name is unique

Thinking Process

  1. Prefix Matching: A folder is a subfolder if its path is a prefix of another folder
    • Efficient for checking if any prefix exists
    • More memory intensive but clearer logic
    • Simpler code, more efficient
  • Strings often need frequency maps or two-pointer scans.
  • Watch index bounds and empty-string edge cases.
  • Stack helps with nested or repeated patterns.
Array + hash map 2 7 11 map hash map for O(1) lookups

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Two pointers on string (this problem) O(n) O(1) Palindrome, parsing
Hash map / frequency O(n) O(k) Anagram, character counts
KMP / rolling hash O(n) O(n) Pattern matching
Stack parsing O(n) O(n) Decode string, parentheses

Solution

struct TrieNode{
    bool isEnd;
    unordered_map<string, TrieNode*> children;
    TrieNode(): isEnd(false){}
};

class Solution {
public:
    Solution(): root(new TrieNode()) {}

    ~Solution() {deleteTrie(root);}

    vector<string> removeSubfolders(vector<string>& folder) {
        for(auto& path: folder) {
            TrieNode* curr = root;
            istringstream iss(path);
            string folderName;

            while(getline(iss, folderName, '/')) {
                if(folderName.empty()) continue;
                if(!curr->children.contains(folderName)) {
                    curr->children[folderName] = new TrieNode();
                }
                curr = curr->children[folderName];
            }
            curr->isEnd = true;
        }
        vector<string> rtn;
        for(auto& path: folder) {
            TrieNode* curr = root;
            istringstream iss(path);
            string folderName;
            bool isSubFolder = false;

            while(getline(iss, folderName, '/')) {
                if(folderName.empty()) continue;
                auto it = curr->children.find(folderName);
                if(it == curr->children.end()) break;
                TrieNode* nextNode = it->second;
                if(nextNode->isEnd && iss.rdbuf()->in_avail() != 0) {
                    isSubFolder = true;
                    break;
                }
                curr = nextNode;
            }
            if(!isSubFolder) rtn.push_back(path);
        }
        return rtn;
    }

private:
    TrieNode* root;

    void deleteTrie(TrieNode* node) {
        if(!node) return;
        for(auto& [_, child]: node->children) {
            deleteTrie(child);
        }
        delete node;
    }
};

Solution Explanation

Approach: Two pointers on string (this problem)

Key idea: 1. Prefix Matching: A folder is a subfolder if its path is a prefix of another folder

How the code works:

  1. Prefix Matching: A folder is a subfolder if its path is a prefix of another folder
    • Efficient for checking if any prefix exists
    • More memory intensive but clearer logic
    • Simpler code, more efficient
    • Strings often need frequency maps or two-pointer scans.
    • Watch index bounds and empty-string edge cases.

Walkthrough — input folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"], expected output ["/a","/c/d","/c/f"]:

Folders “/a/b” is a subfolder of “/a” and “/c/d/e” is inside of folder “/c/d” in our filesystem.

Common Mistakes

  1. Single folder: ["/a"] → ["/a"]
  2. No subfolders: ["/a/b", "/c/d"] → ["/a/b", "/c/d"]
  3. All subfolders: ["/a", "/a/b", "/a/b/c"] → ["/a"]
  4. Similar prefixes: ["/a/b", "/a/bc"] → Both kept (not subfolders)

  5. Deep nesting: ["/a", "/a/b", "/a/b/c", "/a/b/c/d"] → ["/a"]

  6. False prefix match: /a/bc matching /a/b without checking next character
  7. Wrong comparison: Using startsWith without verifying / boundary
  8. Memory leaks: Not deleting trie nodes in C++
  9. Empty string handling: Not skipping empty strings from leading /
  10. Sorting order: Not understanding lexicographic ordering

Key Takeaways

  1. Prefix Matching: A folder is a subfolder if its path is a prefix of another folder
  2. Trie Approach:
    • Efficient for checking if any prefix exists
    • More memory intensive but clearer logic
  3. Sorting Approach:
    • Simpler code, more efficient
    • Leverages lexicographic ordering property
  4. Path Parsing: Use istringstream and getline to split by /
  5. Edge Case: Check that prefix match is followed by / to avoid false positives

References

Template Reference