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.


&nbsp;
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"]


&nbsp;
Constraints:


	1 &lt;= folder.length &lt;= 4 * 104
	2 &lt;= folder[i].length &lt;= 100
	folder[i] contains only lowercase letters and '/'.
	folder[i] always starts with the character '/'.
	Each folder name is unique.


# a TrieNode class for creating new node
class TrieNode():
    def __init__(self):
        self.children = {}
        self.main = False
        
# the main class
class Solution(object):
    def removeSubfolders(self, folder):     
        node = TrieNode()
        res = []
        # sort the list to prevent adding the subfolder to the Trie first
        folder.sort()
        for dir in folder:
            name = dir.split("/")
            if self.addTrie(name,node):
                res.append(dir)
        return res

    # usign the same addTrie template and modify the else part
    def addTrie(self,name,node):    
        trie = node
        for c in name:
            if c not in trie.children:
                trie.children[c] = TrieNode()
            # if char is in trie,
            else:
                # check if it's the last sub folder. 
                if trie.children[c].main == True:
                    return False
            trie = trie.children[c]
        trie.main = True
        return True
class Solution {
    TrieNode root;
    public List<String> removeSubfolders(String[] folder) {
        List<String> res = new ArrayList<>();
        Arrays.sort(folder, (a, b) -> (a.length() - b.length()));
        root = new TrieNode();
        for (String f : folder) {
            if (insert(f)) {
                res.add(f);
            }
        }
        return res;
    }
    
    private boolean insert(String folder) {
        TrieNode node = root;
        char[] chs = folder.toCharArray();
        for (int i = 0; i < chs.length; i++) {
            char ch = chs[i];
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch);
            if (node.isFolder && (i+1 < chs.length && chs[i+1] == '/')) {
                return false;
            }
        }
        node.isFolder = true;
        return true;
    }
}

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isFolder;
}
class Solution {
public:
    
    int check(string &s,unordered_map<string,int>&mp)
    {
        string temp;
        temp.push_back(s[0]); //for maintaining prefix string 
        
        for(int i=1;i<s.size();i++)
        {
            if(s[i]=='/')
            {
                if(mp.count(temp)) //for checking prefix exist in map
                    return true;        
                temp+=s[i];
            }
            else temp+=s[i];
        }
        mp[s]=1;    //if string doesnot exist put it in map
        return false;
    }
    vector<string> removeSubfolders(vector<string>& folder) {
      unordered_map<string,int>mp;
      sort(folder.begin(),folder.end());
     vector<string>ans;
        
        for(auto it:folder)
        {
            if(!check(it,mp))
                ans.push_back(it);
        }
        
        return ans;
        
    }
};
var removeSubfolders = function(folder) {
    folder = folder.sort()
    const result = [];
    for(let i in folder){
        const f = folder[i];
        if(result.length == 0 || !f.startsWith(result[result.length -1] + "/"))
            result.push(f);
    }
    return result;
};
Remove Sub-Folders from the Filesystem