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
dict[str, TrieNode> children
TrieNode(): isEnd(False):
class Solution:
Solution(): root(new TrieNode()) :
~Solution() :deleteTrie(root)
def removeSubfolders(self, folder):
    for path in folder:
        TrieNode curr = root
        istringstream iss(path)
        str folderName
        while getline(iss, folderName, '/'):
            if(not folderName) continue
            if not curr.folderName in children:
                curr.children[folderName] = new TrieNode()
            curr = curr.children[folderName]
        curr.isEnd = True
    list[str> rtn
    for path in folder:
        TrieNode curr = root
        istringstream iss(path)
        str folderName
        bool isSubFolder = False
        while getline(iss, folderName, '/'):
            if(not folderName) continue
            it = curr.children.find(folderName)
            if(it == curr.children.end()) break
            TrieNode nextNode = it.second
            if nextNode.isEnd  and  iss.rdbuf().in_avail() != 0:
                isSubFolder = True
                break
            curr = nextNode
        if not isSubFolder) rtn.append(path:
    return rtn
TrieNode root
def deleteTrie(self, node):
    if(not node) return
    for([_, 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