Given a list of folders, remove all sub-folders in those folders and return in any order the folders after removing.
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.
 
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"]

 
Constraints:

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

Difficulty: interview

Starter code:

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        

Solutions:
class Solution:
    def removeSubfolders(self, folder):
    
        folders = folder
    
        folders.sort()
        output = []
        parent = ' '
    
        for folder in folders:
            if not folder.startswith(parent):
                output.append(folder)
                parent = folder + '/'
    
        return output

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        ans = []
        for i, path in enumerate(sorted(folder)):
            if i == 0 or not path.startswith(ans[-1] + \"/\"):
                ans.append(path)
        return ans

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        return self.first_implementation(folder)
    
    def first_implementation(self, folder: List[str]) -> List[str]:
        \"\"\"
        The directories are not guaranteed to be in sorted order. Sort the input in place with heapsort O(n log n) 
        If they are then this problem goes into O(n) Time
        Benefit of sorting time goes from O(n^2) to O(n log n).
        
        Iterate over the sorted array finding common roots. As long as the next item's root is in the previous 
        remove it.
        \"\"\"
        if not folder:
            return []
        from heapq import heapify, heappop
        heapify(folder)
        # initialize the output though it could be done in true O(1) space with peaking at
        # the previous element in the heap but that would require a pop push
        result = [heappop(folder)]
        
        while folder:
            cur = heappop(folder)
            if not cur.startswith(result[-1] + '/'):
                result.append(cur)
        
        return result
        
        

class Trie:
    def __init__(self):
        self.next={}
        self.end_here=False
    
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        
        def collect(curnode, res, curpath):
            if curnode.end_here:
                res.append('/'.join(curpath))
                return
            
            for folder in curnode.next:
                curpath.append(folder)
                collect(curnode.next[folder], res, curpath)
                curpath.pop()
        
        root=Trie()
        for f in folder:
            cur=root
            for seg in f.split('/'):
                if seg not in cur.next:
                    cur.next[seg]=Trie()
                cur=cur.next[seg]
            cur.end_here=True
            
        res=[]
        
        collect(root, res, [])
        return res

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEnd = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.isEnd = True  
    
    def find(self):
        def dfs(direc, node):
            if node.isEnd:
                answer.append('/' + '/'.join(direc))
                return
            for char in node.children:
                dfs(direc + [char], node.children[char])
        
        answer = []
        dfs([], self.root)
        return answer


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = Trie()
        for f in folder:
            
            f = f.split('/')[1:]
            print(f)
            trie.insert(f)
        return trie.find()

class Trie:
    def __init__(self, *words):
        self._end = '_end'
        self.root = {}
        self.insert(*words)

    def insert(self, *words):
        _end = self._end
        root = self.root

        for word in words:
            current_dict = root
            for letter in word:
                current_dict = current_dict.setdefault(letter, {})
            current_dict[_end] = _end
        return root

    def has(self, word):
        trie = self.root
        _end = self._end

        current_dict = trie
        for letter in word:
            if letter not in current_dict:
                return False
            current_dict = current_dict[letter]
        return _end in current_dict

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        if folder: folder.sort()

        r = []
        trie = Trie()
        for f in folder:
            names = [x for x in f.split('/') if x.strip()]
            to_insert = True
            for i in range(1, len(names)+1):
                subfolder = '/'.join(names[:i])
                subfolder = '/'+subfolder if subfolder else subfolder
                if trie.has(subfolder):
                    to_insert = False
                    break
                
            if to_insert:
                r.append(f)
                trie.insert(f)
        return r


class Node:
    def __init__(self, val):
        self.val = val
        self.children = {}
        self.finished = False
        
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        root = Node(\"\")
        for path in folder:
            paths = path.split(\"/\")
            cur = root
            for each in paths:
                if each == \"\":
                    continue
                if each in cur.children:
                    cur = cur.children[each]
                else:
                    new_node = Node(each)
                    cur.children[each] = new_node
                    cur = new_node
                    
            cur.finished = True
                    
        # get all paths from the root to ...
        folders = []
        def collect(root, path):
            path.append(\"/\"+root.val)
            if root.finished:
                folders.append(list(path))
                path.pop()
                return
            for _, child in root.children.items():
                collect(child, path)
            path.pop()
            
        for _, child in root.children.items():
            collect(child, [])
        return [\"\".join(each) for each in folders]
                
            
                

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        # 1. iterate through the folders in the list
        # 2. split the folder by '/'
        # 3. check if names[:-1] exists in a dict
        # 4. if it exists, skip (drop) the folder
        # 5. if not, add names[:-1] to the dict and add the folder to the output list
        
        d = {}
        for f in folder:
            names = ''.join(f.split('/'))
            if len(names) > 0:
                d[names] = f
        
        output = []
        for f in folder:
            names = ''.join(f.split('/')[:-1])
            if not [True for i in range(len(names)) if names[:i+1] in d]:
                output.append(f)
                
        return output


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:

        def get_key(f):
            
            for i in range(len(f) - 1, -1 , -1):
                if(f[i] == \"/\"):
                    return i
            raise Exception
        
        folder = sorted(folder, key=lambda x : len(x))
        top_level_folders = {}
        
        for f in folder:
            
            key = get_key(f)
            parent = f[0:key]
            check = False
            while(parent):
                
                if(parent in top_level_folders):
                    check = True
                key = get_key(parent)
                parent = f[0:key]
            
            if(not check):
                top_level_folders[f] = True
            
            
            
        ret = []
        for key in top_level_folders:
            ret.append(key)
        return ret

class Solution:
    def init(self, folder):
        self.tries = {}
        for f_ in folder:
            f_list = list(filter(None, (f_.strip()+'/$').split(\"/\")))
            node = self.tries
            for folder in f_list:
                if folder not in node:
                    node[folder] = {}
                node = node[folder]

    def removeSubfolders(self, folder: List[str]) -> List[str]:
        result = []
        if folder == None or len(folder) == 0:
            return result
        
        self.init(folder)
        for f_ in folder:
            path = []
            node = self.tries
            f_list = list(filter(None, f_.strip().split(\"/\")))
            for folder in f_list:
                if '$' in node:
                    break
                path.append(folder)
                node = node[folder]

            if \"/\"+\"/\".join(path) not in result:
                result.append(\"/\"+\"/\".join(path))
            
        return result
                



        
        

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = {}
        trie[\"/\"] = False   # whether it's a folder
        
        for f in folder:
            paths = f.split(\"/\")
            current = trie
            n = len(paths)
            for i in range(1,n):
                p = paths[i]
                if p not in current:
                    current[p] = {}
                current = current[p]
                if i==n-1:  current[\"/\"] = True
                else:
                    if \"/\" not in current:  current[\"/\"] = False
                
                
        print(trie)
        
        self.ans = []
        def findPath(path, result):
            if path[\"/\"]:
                self.ans.append(result)
                return
            for k, v in path.items():
                if k == \"/\":    continue
                findPath(v, result+[k])
            
        result = []
        findPath(trie, result)
        return [\"/\" + \"/\".join(a) for a in self.ans]
            

class Solution:
    def init(self, folder):
        self.tries = {}
        for f_ in folder:
            f_list = list(filter(None, f_.strip().split(\"/\")))
            node = self.tries
            for folder in f_list:
                if folder not in node:
                    node[folder] = {}
                node = node[folder]
            node['$'] = {'$'}

    def removeSubfolders(self, folder: List[str]) -> List[str]:
        result = []
        if folder == None or len(folder) == 0:
            return result
        
        self.init(folder)
        for f_ in folder:
            path = []
            node = self.tries
            f_list = list(filter(None, f_.strip().split(\"/\")))
            for folder in f_list:
                if '$' in node:
                    break
                path.append(folder)
                node = node[folder]

            if \"/\"+\"/\".join(path) not in result:
                result.append(\"/\"+\"/\".join(path))
            
        return result
                



        
        

class Trie:
    
    def __init__(self):
        self.root = {}
        
    def insert(self, word):
        cur = self.root
        for ch in word:
            if ch not in cur:
                cur[ch] = {}
            cur = cur[ch]
        cur['END'] = {}
        
    def search(self):
        
        def dfs(node, tmp, res):
            if 'END' in node:
                res.append(''.join(tmp))
            else:
                for ch in node:
                    tmp.append(ch)
                    dfs(node[ch], tmp, res)
                    tmp.pop()
            
        res, tmp = [], []
        dfs(self.root, tmp, res)
        return res

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        t = Trie()
        for f in folder:
            t.insert(f + '/')
        return [f[:-1] for f in t.search()]
        
        
        # init
        n = len(folder)
        
        # sort the folder
        folder = [f + '/' for f in folder]
        folder.sort()
        
        parent = 0
        for child in range(1, n):
            if folder[child].startswith(folder[parent]):
                folder[child] = None
            else:
                parent = child
        
        return [f[:-1] for f in folder if f is not None]


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()
        res = []
        for x in folder:
            cur = x.split('/')
            if not res or res[-1] != cur[:len(res[-1])]:
                res.append(cur)
        
        return [ \"/\".join(x) for x in res ]
            
        

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        d = {}
        ret = []
        folder.sort()
        for f in folder:
            fl = f.split(\"/\")
            for i in range(1, len(fl)):
                tup = tuple(fl[1:i+1])
                tup_h = tuple(tup)
                if tup_h in d:
                    #print(\"this is a subfolder: \", end=\" \")
                    #print(tup_h)
                    
                    break
                elif i == len(fl)-1:
                    #print(\"this is new: \", end=\" \")
                    #print(tup_h)
                    d[tup_h] = f
                    ret.append(f)
                
            
           # d[f_t] = 0
        #print(d)
        return ret

class Node:
    def __init__(self, val):
        self.val = val
        self.children = {}
        self.finished = False
        
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        root = Node(\"\")
        for path in folder:
            paths = path.split(\"/\")
            cur = root
            for each in paths:
                if each == \"\":
                    continue
                if each in cur.children:
                    cur = cur.children[each]
                else:
                    new_node = Node(each)
                    cur.children[each] = new_node
                    cur = new_node
                    
            cur.finished = True
                    
        # get all paths from the root to ...
        folders = []
        def collect(root, path):
            if root.finished:
                folders.append(path+\"/\"+root.val)
                return
            for _, child in root.children.items():
                collect(child, path+\"/\"+root.val)
            
        for _, child in root.children.items():
            collect(child, \"\")
        return folders
            
                

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort(key = lambda x:len(x))
        folderDict = {}
        ans = set(folder)
        
        # ans = []
        for address in folder:
            aList = (address[1:]).split('/')
            # print(address, aList)
            pointer = folderDict
            for name in aList:
                if name in pointer:
                    pointer = pointer[name]
                    if '$' in pointer:
                        if address in ans:
                            # print('remove', address)
                            ans.remove(address)
                else:
                    pointer[name] = {}
                    pointer = pointer[name]
            pointer['$'] = ''
        # print(folderDict)
        return ans

class TrieNode:
    def __init__(self, val):
        self.val = val
        self.children = {}
        self.isWord = False

class Trie:
    def __init__(self):
        self.root = TrieNode('$')
        self.answer = []
    
    def insert(self, word):
        root = self.root
        for w in word:
            if w not in root.children:
                root.children[w] = TrieNode(w)
            root = root.children[w]
        root.isWord = True
    
    def getCommonPrefix(self, root, prefix):
        if root.isWord:
            self.answer.append(prefix)  #If the current node is a folder end, then just get the prefix till here and ignore the further path.
            return
        
        children = root.children
        for c in children:
            self.getCommonPrefix(children[c], prefix+\"/\"+ children[c].val)
        
                
class Solution(object):
    def removeSubfolders(self, folders):
        \"\"\"
        :type folder: List[str]
        :rtype: List[str]
        \"\"\"
        trie = Trie()
        
        for f in folders:
            path = f.split(\"/\")
            path.pop(0)
            trie.insert(path)
        
        trie.getCommonPrefix(trie.root, \"\")
        
        return trie.answer
            
        
        
        
        
        
        
        
        
        # folder=sorted(folder)
        # ans=[]
        # for i in folder:
        #     flag=1
        #     for ele in ans:
        #         if(i.startswith(ele) and i[len(ele)]==\"/\"):
        #             flag=0
        #             break
        #     if(flag==1):
        #         ans.append(i)
        #     # print(ans)
        # return ans

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        class Node:
            def __init__(self):
                self.is_path = False
                self.subs = {}
            
            def add_path(self, p, i=0):
                if i == len(p): return
                n = p[i]
                if n not in self.subs:
                    self.subs[n] = Node()
                self.subs[n].is_path |= (len(p) - i == 1)
                self.subs[n].add_path(p, i+1)
                
        
        t = Node()
        for f in folder:
            p = f.split('/')[1:]
            t.add_path(p)
        s = []
        p = []
        def dfs_visit(r, name=''):
            if r.is_path is True:
                s.append('/'.join(p)+'/'+name)
                return
            p.append(name)
            for sub_name, sub in r.subs.items():
                dfs_visit(sub, sub_name)
            p.pop()
        dfs_visit(t)
        return s

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEnd = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.isEnd = True  
    
    def find(self):
        def dfs(direc, node):
            if node.isEnd:
                answer.append('/' + '/'.join(direc))
                return
            for char in node.children:
                dfs(direc + [char], node.children[char])
        
        answer = []
        dfs([], self.root)
        return answer


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = Trie()
        for f in folder:
            f = f.split('/')[1:]
            trie.insert(f)
        return trie.find()

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, path):
        node = self.root
        
        for ch in path:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            
            node = node.children[ch]
        
        node.end = '/'+'/'.join(path)
    
    def find(self):        
        def dfs(aggregate, node):
            if node.end:
                result.append(node.end)
                return
            
            for ch in node.children:
                dfs(aggregate+[ch], node.children[ch])
        
        result = []
        dfs([], self.root)
        return result
    
    

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        if not folder:
            return []
        
        trie = Trie()
        for path in folder:
            splitPaths = path.split('/')[1:]
            trie.insert(splitPaths)
        
        returnList = trie.find()
        
        return returnList


class Node:
    def __init__(self, name):
        self.name = name
        self.next = dict()
        self.flag = False
        
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        head = dict()
        for f in folder:
            sub = f.split(\"/\")
            for i in range(1,len(sub)): # first element is empty string, skip
                            
                if i == 1: # first node
                    node = head.setdefault(sub[i], Node(sub[i]))
                else:
                    node = node.next.setdefault(sub[i], Node(sub[i]))
                    
                if i == len(sub)-1:
                    node.flag = True

        ret = list()
        # for k in head:
        #     # dfs
        #     stack = [(head[k], list())]
        #     while stack:
        #         node, chain = stack.pop()
        #         chain.append(node.name)
        #         if node.flag:
        #             ret.append(\"/\"+\"/\".join(chain))
        #         else:
        #             for k, next_node in node.next.items():
        #                 stack.append((next_node, list(chain)))
        
        
        def backtrack(node):
            if node.flag:
                return [[node.name]]
            
            ret = list()
            for k,v in node.next.items():
                l = backtrack(v)
                for i in range(len(l)):
                    l[i].append(node.name)
                ret.extend(l)
            return ret
                    
                
        for k, v in head.items():
            # dfs
            for l in backtrack(v):
                ret.append(\"/\" + \"/\".join(l[::-1]))

        return ret
    
    
            
                    
                
                
                
                
        

class Node:
    def __init__(self, name):
        self.name = name
        self.next = dict()
        self.flag = False
        
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        head = dict()
        for f in folder:
            sub = f.split(\"/\")
            for i in range(1,len(sub)): # first element is empty string, skip
                            
                if i == 1: # first node
                    node = head.setdefault(sub[i], Node(sub[i]))
                else:
                    node = node.next.setdefault(sub[i], Node(sub[i]))
                    
                if i == len(sub)-1:
                    node.flag = True

        ret = list()
        # for k in head:
        #     # dfs
        #     stack = [(head[k], list())]
        #     while stack:
        #         node, chain = stack.pop()
        #         chain.append(node.name)
        #         if node.flag:
        #             ret.append(\"/\"+\"/\".join(chain))
        #         else:
        #             for k, next_node in node.next.items():
        #                 stack.append((next_node, list(chain)))
        
        
        def backtrack(node):
            if node.flag:
                return [[node.name]]
            
            ans = list()
            for k,v in node.next.items():
                l = backtrack(v)
                for i in range(len(l)):
                    l[i].append(node.name)
                ans.extend(l)
            return ans
                    
                
        for k, v in head.items():
            # dfs
            for l in backtrack(v):
                ret.append(\"/\" + \"/\".join(l[::-1]))

        return ret
    
    
            
                    
                
                
                
                
        

class Node:
    def __init__(self, name):
        self.name = name
        self.next = dict()
        self.flag = False
        
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        head = dict()
        for f in folder:
            sub = f.split(\"/\")
            for i in range(1,len(sub)): # first element is empty string, skip
                            
                if i == 1: # first node
                    node = head.setdefault(sub[i], Node(sub[i]))
                else:
                    node = node.next.setdefault(sub[i], Node(sub[i]))
                    
                if i == len(sub)-1:
                    node.flag = True

        ret = list()
        # for k in head:
        #     # dfs
        #     stack = [(head[k], list())]
        #     while stack:
        #         node, chain = stack.pop()
        #         chain.append(node.name)
        #         if node.flag:
        #             ret.append(\"/\"+\"/\".join(chain))
        #         else:
        #             for k, next_node in node.next.items():
        #                 stack.append((next_node, list(chain)))
        
        
        def backtrack(node):
            if node.flag:
                
                return [[node.name]]
            
            ret = list()
            for k,v in node.next.items():
                l = backtrack(v)
                for i in range(len(l)):
                    l[i].append(node.name)
                ret.extend(l)
            return ret
                    
                
        ret = list()
        for k, v in head.items():
            # dfs

            for l in backtrack(v):
                ret.append(\"/\" + \"/\".join(l[::-1]))

        return ret
    
    
            
                    
                
                
                
                
        

class Solution:
    
    def is_subfolder(self, parent, current):
        if parent == \"\":
            return False
        
        splitted = current.split(parent)
        
        if len(splitted) == 1:
            return False
        
        if splitted[0] == \"\":
            if splitted[1] == \"\":
                return True
            elif len(splitted[1]) > 0:
                if splitted[1][0] == \"/\":
                    return True
        return False
        
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()
        parent = folder[0]
        
        output = []
        output.append(parent)
        
        index  = 1
        
        while(index < len(folder)):
            current = folder[index]
            
            if not self.is_subfolder(parent, current):
                output.append(current)
                parent = current
            
            index += 1
        return output

class Node:
    def __init__(self, name):
        self.name = name
        self.next = dict()
        self.flag = False
        
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        head = dict()
        for f in folder:
            sub = f.split(\"/\")
            for i in range(1,len(sub)): # first element is empty string, skip
                            
                if i == 1: # first node
                    node = head.setdefault(sub[i], Node(sub[i]))
                else:
                    node = node.next.setdefault(sub[i], Node(sub[i]))
                    
                if i == len(sub)-1:
                    node.flag = True

        ret = list()
        for k in head:
            # dfs
            stack = [(head[k], list())]
            while stack:
                node, chain = stack.pop()
                chain.append(node.name)
                if node.flag:
                    ret.append(\"/\"+\"/\".join(chain))
                else:
                    for k, next_node in node.next.items():
                        stack.append((next_node, list(chain)))

        return ret
            
                    
                
                
                
                
        

class Node:
    def __init__(self, name):
        self.name = name
        self.next = dict()
        self.flag = False
        
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        head = dict()
        for f in folder:
            sub = f.split(\"/\")

            for i in range(1,len(sub)):

                # first node
                if i == 1:
                    node = head.setdefault(sub[i], Node(sub[i]))
                # not first node
                else:
                    print
                    node = node.next.setdefault(sub[i], Node(sub[i]))
                    # print(node.next)
                    
                if i == len(sub)-1:
                    node.flag = True
                # if 1 < 1 < len(sub)-1:
                #     node = next_node


        print(head) 
        ret = list()
        for k in head:
            # dfs
            stack = [(head[k], list())]
            while stack:
                node, chain = stack.pop()
                chain.append(node.name)
                if node.flag:
                    ret.append(\"/\"+\"/\".join(chain))
                else:
                    for k, next_node in node.next.items():
                        stack.append((next_node, list(chain)))

        return ret
            
                    
                
                
                
                
        

class Node:
    def __init__(self, name):
        self.name = name
        self.next = dict()
        self.flag = False
        
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        head = dict()
        for f in folder:
            sub = f.split(\"/\")
            for i in range(1,len(sub)): # first element is empty string, skip
                            
                if i == 1: # first node
                    node = head.setdefault(sub[i], Node(sub[i]))
                else:
                    node = node.next.setdefault(sub[i], Node(sub[i]))
                    
                if i == len(sub)-1:
                    node.flag = True

        ret = list()
        # for k in head:
        #     # dfs
        #     stack = [(head[k], list())]
        #     while stack:
        #         node, chain = stack.pop()
        #         chain.append(node.name)
        #         if node.flag:
        #             ret.append(\"/\"+\"/\".join(chain))
        #         else:
        #             for k, next_node in node.next.items():
        #                 stack.append((next_node, list(chain)))
        
        
        def backtrack(node):
            if node.flag:
                return [[node.name]]
            
            ret = list()
            for k,v in node.next.items():
                l = backtrack(v)
                for i in range(len(l)):
                    l[i].append(node.name)
                ret.extend(l)
            return ret
                    
                
        ret = list()
        for k, v in head.items():
            # dfs
            for l in backtrack(v):
                ret.append(\"/\" + \"/\".join(l[::-1]))

        return ret
    
    
            
                    
                
                
                
                
        

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEnd = False
        
        
class Trie:
    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.isEnd = True
        
    def find(self):
        def dfs(path, node):
            if node.isEnd:
                ans.append('/' + '/'.join(path))
                return 
            for c in node.children:
                dfs(path + [c], node.children[c])
                
        ans = []
        dfs([], self.root)
        return ans


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = Trie()
        for f in folder:
            f = f.split('/')[1:]
            trie.insert(f)
        return trie.find()

class Node():
    def __init__(self):
        self.next = {}
        self.folder = False

class Trie():
    def __init__(self):
        self.root = Node()
    
    def update(self, folder):
        
        start = 1
        node = self.root
        while node and start < len(folder):
            i = start
            while i<len(folder) and folder[i]!= '/':
                i += 1
            curr_fold = folder[start:i]
            
            if curr_fold not in node.__next__:
                node.next[curr_fold] = Node()
            
            node = node.next[curr_fold]
            start = i+1
        node.folder = True
        
    
    def find_all(self):
        output = []
        
        def helper(node, path):
            if node.folder:
                output.append(path)
            else:
                for next_node in node.__next__:
                    helper(node.next[next_node], path+'/'+next_node)
        
        helper(self.root, '')
        return output
    
        
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        
        folder_trie = Trie()
        for fold in folder:
            folder_trie.update(fold)
            
        return folder_trie.find_all()


class TrieNode:
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.isEnd = False

class Solution:
    def __init__(self):
        self.root = TrieNode()
    
    def add(self, path):
        node = self.root
        for p in path:
            node = node.children[p]
        node.isEnd = True
        
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        for f in folder:
            f = f.split(\"/\")[1:]
            self.add(f)
        
        ans = []
        self.dfs(self.root, [], ans)
        return ans
    
    def dfs(self, node, path, ans):
        if node.isEnd:
            ans.append(\"/\" + \"/\".join(path))
            return
        
        for c in node.children:
            self.dfs(node.children[c], path + [c], ans)
        
        

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()
        
        res = [folder.pop(0)]
        n = len(folder)
        
        for i in range(n):
            pattern = f'^{res[-1]}/'
            result = re.match(pattern, folder[i])
            if not result: 
                res += [folder[i]]
            
        return res
        


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()
        
        n = len(folder)
        prev = folder[0]
        
        i = 1
        while i < n:
            curr = folder[i]
            
            if curr.startswith(prev + '/'):
                folder.remove(curr)
                curr = prev
                i-= 1
                n-= 1
                            
            prev = curr
            i+= 1
        
        return folder

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()
        #print(folder)
        l = len(folder) 
        i=0
        while(i<l-1):
            p = folder[i]
            j = i+1
            l = len(folder)           
            while(j<l):
                if folder[j].startswith(p):
                    if len(folder[j])>len(p) and folder[j][len(p)]=='/':
                        folder.remove(folder[j])
                        l = len(folder)
                    else:
                        j+=1
                else:
                    break
                
            i+=1
        return folder
            
        


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        s = set()
        folder.sort(key=len)
        for i in folder:
            f = 0
            x = i.split('/')
            temp = \"\"
            for j in x:
                if j==\"\":
                    continue
                temp = temp + '/'+j
                if temp in s:
                    f = 1
                    break
            if f==0:
                s.add(i)
        return list(s)

# O(M*N)
class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEnd = False


class Solution:
    def __init__(self):
        self.root = TrieNode()

    def _add(self, path):
        node = self.root
        for string in path.split('/'):
            if not string:
                continue
            if string not in node.children:
                node.children[string] = TrieNode()
            node = node.children[string]
        node.isEnd = True
        return

    def _isSubFolder(self, path):
        node = self.root
        for string in path.split('/'):
            if not string:
                continue
            if node.isEnd:
                return True
            node = node.children[string]
        return False

    def removeSubfolders(self, folder: List[str]) -> List[str]:
        res = []
        for path in folder:
            self._add(path)
        for path in folder:
            if not self._isSubFolder(path):
                res.append(path)
        return res

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        sort = sorted(folder, key = len)
        
        visited = []
        
        for f in sort:
            found = False
            for prefix in visited:
                if f.startswith(prefix + \"/\"):
                    found = True
                    break
            if not found:
                visited.append(f)
        return visited

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()
        folder_set = set(folder)
        
        n = len(folder)
        prev = folder[0]
        
        i = 1
        while i < n:
            curr = folder[i]
            
            len_prev, len_curr = len(prev), len(curr)
            if len_prev < len_curr:
                if curr[:len_prev] in folder_set:
                    if curr[len_prev] == '/':
                        folder.remove(curr)
                        curr = prev
                        i-= 1
                        n-= 1
                            
            prev = curr
            i+= 1
        
        return folder

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()
        folder_set = set(folder)
        
        n = len(folder)
        prev = folder[0]
        
        i = 1
        while i < n:
            curr = folder[i]
            
            if curr.startswith(prev + '/'):
                folder.remove(curr)
                curr = prev
                i-= 1
                n-= 1
                            
            prev = curr
            i+= 1
        
        return folder

class Solution:
    def removeSubfolders(self, folders: List[str]) -> List[str]:
        seen = set()
        # folders.sort(key = lambda x: len(x.split('/')))
        folders.sort(key = lambda x: len(x))
        # print(folders)
        for folder in folders.copy():
            # print(folder)
            # folder_split = folder.split('/')[1:]
            for i in range(2, len(folder)):
                if folder[i] == '/' and folder[:i] in seen: 
                    folders.remove(folder)
                    break
            else: seen.add(folder)
            # print(seen)
                    
        return folders

class Solution:
    def removeSubfolders(self, folders: List[str]) -> List[str]:
        seen = set()
        # folders.sort(key = lambda x: len(x.split('/')))
        folders.sort(key = lambda x: len(x))
        # print(folders)
        for folder in folders.copy():
            # print(folder)
            folder_split = folder.split('/')[1:]
            for i in range(len(folder_split)):
                if tuple(folder_split[:i+1]) in seen: 
                    folders.remove(folder)
                    break
            else: seen.add(tuple(folder_split))
            # print(seen)
                    
        return folders

class Trie:
    def __init__(self):
        self.root = {\"*\": \"*\"}

    def add(self, word):
        current = self.root
        for letter in word:
            if letter not in current:
                current[letter] = {}
            current = current[letter]
        current[\"*\"] = \"*\"

    def has(self, word):
        current = self.root
        for letter in word:
            if letter not in current:
                return False
            current = current[letter]

        return \"*\" in current

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:        
        trie = Trie()
        for fol in folder:
            trie.add(fol)
        
        response = set()
        for fol in folder:
            key = fol[:fol.rindex(\"/\")]
            while key:
                if trie.has(key):
                    break
                key = key[:key.rindex(\"/\")]
            
            if not key:
                response.add(fol)
                
            # if not key:
            #     response.add(fol)
            # if not trie.has(key):
            #     response.add(fol)
                
        return response

class Trie:
    def __init__(self):
        self.root = {\"*\": \"*\"}

    def add(self, word):
        current = self.root
        for letter in word:
            if letter not in current:
                current[letter] = {}
            current = current[letter]
        current[\"*\"] = \"*\"

    def has(self, word):
        current = self.root
        for letter in word:
            if letter not in current:
                return False
            current = current[letter]

        return \"*\" in current

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:        
        trie = Trie()
        for fol in folder:
            trie.add(fol)
        
        response = set()
        for fol in folder:
            key = fol[:fol.rindex(\"/\")]
            while key:
                if trie.has(key):
                    break
                key = key[:key.rindex(\"/\")]
            
            if not key:
                response.add(fol)
                
        del trie
        return response

class Trie:
    def __init__(self):
        self.sub = collections.defaultdict(Trie)
        self.index = -1

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        self.root = Trie()
        
        for i in range(len(folder)):
            cur = self.root
            for c in folder[i]:
                cur = cur.sub[c]
            cur.index = i
        
        return self.bfs(self.root, folder)
    
    
    def bfs(self, trie: Trie, folder: List[str]) -> List[str]:
        q, ans = [trie], []
        for t in q:
            if t.index >= 0:
                ans.append(folder[t.index])
            for c in t.sub.keys():
                if '/' != c or t.index < 0:
                    q.append(t.sub.get(c))
        return ans

class Trie:
    def __init__(self):
        self.sub = collections.defaultdict(Trie)
        self.index = -1

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        self.root = Trie()
        for i in range(len(folder)):
            cur = self.root
            for c in folder[i]:
                cur = cur.sub[c]
            cur.index = i
        return self.bfs(self.root, folder)
    def bfs(self, trie: Trie, folder: List[str]) -> List[str]:
        q, ans = [trie], []
        for t in q:
            if t.index >= 0:
                ans.append(folder[t.index])
            for c in t.sub.keys():
                if '/' != c or t.index < 0:
                    q.append(t.sub.get(c))
        return ans

class Trie:
    def __init__(self):
        self.sub = collections.defaultdict(Trie)
        self.index = -1
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        self.root = Trie()
        for i in range(len(folder)):
            cur = self.root
            for c in folder[i]:
                cur = cur.sub[c]
            cur.index = i
        return self.bfs(self.root, folder)
    def bfs(self, trie: Trie, folder: List[str]) -> List[str]:
        q, ans = [trie], []
        for t in q:
            if t.index >= 0:
                ans.append(folder[t.index])
            for c in list(t.sub.keys()):
                if '/' != c or t.index < 0:
                    q.append(t.sub.get(c))
        return ans
        # folder.sort()
        # ans = []
        # for f in folder:
        #     if not ans or not f.startswith(ans[-1] + '/'):
        #         ans.append(f)
        # return ans
        

        
        # folder.sort()
        # seen = set()
        # for path in folder:
        #     if not any(path[i] == '/' and path[:i] in seen for i in range(2, len(path))):
        #         seen.add(path)
        # return seen
    
                
#Trie
#         trie = {}
#         for path in folder:
#             curr = trie
#             for f in path.split('/'):
#                 if f in curr:
#                     curr = curr[f]
#                 else:
#                     curr[f] = {}
#                     curr = curr[f]
#             curr[None] = None
        
#         res = []
#         for path in folder:
#             curr = trie
#             issub = False
#             for f in path.split('/'):
#                 if None in curr: 
#                     issub = True
#                 else:
#                     curr = curr[f]
#             if not issub:
#                 res.append(path)
                
#         return res
            
            
            
            
        
        
        
                
                
            
            
            


class Solution1:
    #1.Sort the folders;
    #2. For each folder check if the followings are child folders; if yes, ignore; otherwise, count it in
    \"\"\"
    I think the time complexity for method 2 is actually O(n * m * logn).
    Because the sort is based on merge sort for Object and time complexity of merge sort is O(n * logn). That means n * logn times comparing happened.
    For this question, it just makes the comparing time be O(m). Thus it won't increase the number of \"layers\" of merge sort to log(n * m).

    Time: O(n * m * log(n)), space: O(1)(excluding space cost of sorting part), where n = folder.length, m = average size of the strings in folder.

    \"\"\"
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        ans = []
        folder.sort()
        for f in folder:
            if not ans or not f.startswith(ans[-1] + '/'): #need '/' to ensure a parent.
                ans.append(f)
        return ans
    
    
class Trie:
    def __init__(self):
        self.sub = collections.defaultdict(Trie)
        self.index = -1

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        self.root = Trie()
        for i in range(len(folder)):
            cur = self.root
            for c in folder[i]:
                cur = cur.sub[c]
            cur.index = i
        return self.bfs(self.root, folder)
    def bfs(self, trie: Trie, folder: List[str]) -> List[str]:
        q, ans = [trie], []
        for t in q:
            if t.index >= 0:
                ans.append(folder[t.index])
            for c in t.sub.keys():
                if '/' != c or t.index < 0:
                    q.append(t.sub.get(c))
        return ans

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder_subs = []
        folder.sort(key=len)
        for f in folder:
            flag = False
            for j in folder_subs:
                if f.startswith(j + '/'):
                    flag = True
                    break
            if not flag:
                folder_subs.append(f)
                    
        return folder_subs

class Trie:
    def __init__(self):
        self.sub = collections.defaultdict(Trie)
        self.index = -1
    
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        root = Trie()
        for i in range(len(folder)):
            curr = root
            for c in folder[i]:
                curr = curr.sub[c]
            curr.index = i
        q, res = [root], []
        for t in q:
            if t.index >= 0:
                res.append(folder[t.index])
            for c in t.sub.keys():
                if c != '/' or t.index < 0:
                    q.append(t.sub.get(c))
        return res

class Solution:
    def removeSubfolders(self, folders: List[str]) -> List[str]:
        dirs = set()
        folders = sorted(list(filter(None,folder.split('/'))) for folder in folders)
        
        print(folders)
        
        for folder_fp in folders:
            curr_name = \"\"
            for folder in folder_fp:
                curr_name += f\"/{folder}\"
                if curr_name in dirs:
                    break
            else:
                dirs.add(curr_name)
            #print(dirs)
        return dirs

class Trie:
    def __init__(self):
        self.children = collections.defaultdict(Trie)
        self.index = -1
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        self.root = Trie()
        
        for i, f in enumerate(folder):
            curr = self.root
            for ch in f:
                curr = curr.children[ch]
            curr.index = i
        # print(self.root)
        return self.bfs(self.root, folder)
        
    def bfs(self, trie, folder):
        q = [trie]
        res = []
        
        for node in q:
            if node.index >= 0:
                res.append(folder[node.index])
                for c in node.children:
                    if c != '/':
                        q.append(node.children[c])
            else:
                for c in node.children:
                    # if c != '/':
                    q.append(node.children[c])
        return res
# class Trie:
#     def __init__(self):
#         self.sub = collections.defaultdict(Trie)
#         self.index = -1
# class Solution:
#     def removeSubfolders(self, folder: List[str]) -> List[str]:
#         self.root = Trie()
#         for i in range(len(folder)):
#             curr = self.root
#             for ch in folder[i]:
#                 curr = curr.sub[ch]
#             curr.index = i
#         return self.bfs(self.root, folder)
    
#     def bfs(self, node, folder):
#         q, ans = [node], []
#         for t in q:
#             if t.index >= 0:
#                 ans.append(folder[t.index])
#             # else:
#             for c in t.sub:
#                 if c != '/' or t.index < 0:
#                     q.append(t.sub.get(c))
#         return ans


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder_subs = []
        folder_k = sorted(folder, key=len)
        for f in folder_k:
            flag = False
            for j in folder_subs:
                if f.startswith(j + '/'):
                    flag = True
                    break
            if not flag:
                folder_subs.append(f)
                    
        return folder_subs

class Trie:
    def __init__(self):
        self.sub = collections.defaultdict(Trie)
        self.index = -1
    
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        root = Trie()
        for i in range(len(folder)):
            curr = root
            for c in folder[i]:
                curr = curr.sub[c]
            curr.index = i
        q, res = [root], []
        for t in q:
            if t.index >= 0:
                res.append(folder[t.index])
            for c in t.sub:
                if c != '/' or t.index < 0:
                    q.append(t.sub.get(c))
        return res

class Solution:
    def removeSubfolders(self, folders: List[str]) -> List[str]:
        
        folders.sort()
        first = folders[0]
        res_set = set()
        res_set.add(first)
        for i in range(1, len(folders)):
            folder = folders[i]
            if folder.startswith(first) and folder.count('/') > first.count('/'):
                pass
            else:
                res_set.add(folder)
                res_set.add(first)
                first = folder
        
        res = list(res_set)
        res.sort()
        return res

class Trie:
    def __init__(self):
        self.children = collections.defaultdict(Trie)
        self.index = -1
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        self.root = Trie()
        
        for i, f in enumerate(folder):
            curr = self.root
            for ch in f:
                curr = curr.children[ch]
            curr.index = i
        # print(self.root)
        return self.bfs(self.root, folder)
        
    def bfs(self, trie, folder):
        q = [trie]
        res = []
        
        for node in q:
            if node.index >= 0:
                res.append(folder[node.index])
            # else:
            for c in node.children:
                if c != '/' or node.index == -1:
                    q.append(node.children.get(c))
        return res
# class Trie:
#     def __init__(self):
#         self.sub = collections.defaultdict(Trie)
#         self.index = -1
# class Solution:
#     def removeSubfolders(self, folder: List[str]) -> List[str]:
#         self.root = Trie()
#         for i in range(len(folder)):
#             curr = self.root
#             for ch in folder[i]:
#                 curr = curr.sub[ch]
#             curr.index = i
#         return self.bfs(self.root, folder)
    
#     def bfs(self, node, folder):
#         q, ans = [node], []
#         for t in q:
#             if t.index >= 0:
#                 ans.append(folder[t.index])
#             # else:
#             for c in t.sub:
#                 if c != '/' or t.index < 0:
#                     q.append(t.sub.get(c))
#         return ans


class Solution1:
    #1.Sort the folders;
    #2. For each folder check if the followings are child folders; if yes, ignore; otherwise, count it in
    \"\"\"
    I think the time complexity for method 2 is actually O(n * m * logn).
    Because the sort is based on merge sort for Object and time complexity of merge sort is O(n * logn). That means n * logn times comparing happened.
    For this question, it just makes the comparing time be O(m). Thus it won't increase the number of \"layers\" of merge sort to log(n * m).

    Time: O(n * m * log(n)), space: O(1)(excluding space cost of sorting part), where n = folder.length, m = average size of the strings in folder.

    \"\"\"
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        ans = []
        folder.sort()
        for f in folder:
            if not ans or not f.startswith(ans[-1] + '/'): #need '/' to ensure a parent.
                ans.append(f)
        return ans
    
    
class Trie:
    def __init__(self):
        self.sub = collections.defaultdict(Trie)
        self.index = -1

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        self.root = Trie()
        for i in range(len(folder)):
            cur = self.root
            for c in folder[i]:
                cur = cur.sub[c]
            cur.index = i
        return self.bfs(self.root, folder)
    def bfs(self, trie: Trie, folder: List[str]) -> List[str]:
        q, ans = [trie], []
        for t in q:
            if t.index >= 0:
                ans.append(folder[t.index])
            for c in t.sub.keys():
                if '/' != c or t.index < 0:
                    q.append(t.sub.get(c))
        return ans

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEnd = False

class Trie3:
    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.isEnd = True  
    
    def find(self):
        def dfs(direc, node):
            if node.isEnd:
                answer.append('/' + '/'.join(direc))
                return
            for char in node.children:
                dfs(direc + [char], node.children[char])
        
        answer = []
        dfs([], self.root)
        return answer


class Solution3:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = Trie()
        for f in folder:
            f = f.split('/')[1:]
            trie.insert(f)
        return trie.find()

# class Trie:
#     def __init__(self):
#         self.children = collections.defaultdict(Trie)
#         self.index = -1
# class Solution:
#     def removeSubfolders(self, folder: List[str]) -> List[str]:
#         self.root = Trie()
        
#         for i, f in enumerate(folder):
#             curr = self.root
#             for ch in f:
#                 curr = curr.children[ch]
#             curr.index = i
#         # print(self.root)
#         return self.bfs(self.root, folder)
        
#     def bfs(self, trie, folder):
#         q = [trie]
#         res = []
        
#         for node in q:
#             if node.index >= 0:
#                 res.append(folder[node.index])
#             else:
#                 for c in node.children:
#                     q.append(c)
#         return res
class Trie:
    def __init__(self):
        self.sub = collections.defaultdict(Trie)
        self.index = -1
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        self.root = Trie()
        for i in range(len(folder)):
            curr = self.root
            for ch in folder[i]:
                curr = curr.sub[ch]
            curr.index = i
        return self.bfs(self.root, folder)
    
    def bfs(self, node, folder):
        q, ans = [node], []
        for t in q:
            if t.index >= 0:
                ans.append(folder[t.index])
            # else:
            for c in t.sub.keys():
                if c != '/' or t.index < 0:
                    q.append(t.sub.get(c))
        return ans

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        # 
        class TrieNode:
            def __init__(self):
                self.children = defaultdict(TrieNode)
                self.index = -1
        res = []
        root = TrieNode()
        for i in range(len(folder)):
            trie = root
            for c in folder[i]:
                trie = trie.children[c]
            trie.index = i
        res = []
        
        # bfs
        q = [root]
        while q:
            node = q.pop(0)
            if node.index != -1:
                res.append(folder[node.index])
            # 文件名可能包含多个字符
            # [\"/a/b/c\",\"/a/b/ca\",\"/a/b/d\"]
            for c in node.children.keys():
                if node.index < 0 or c!='/':
                    q.append(node.children[c])
                
        return res

class Trie:
    def __init__(self):
        self.root = {\"*\": \"*\"}

    def add(self, word):
        current = self.root
        for letter in word:
            if letter not in current:
                current[letter] = {}
            current = current[letter]
        current[\"*\"] = \"*\"

    def has(self, word):
        current = self.root
        for letter in word:
            if letter not in current:
                return False
            current = current[letter]

        return \"*\" in current

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:        
        # folder = sorted(folder1, key=len) 
        trie = Trie()
        for fol in folder:
            trie.add(fol)
        
        response = list()
        response_obj = {}
        # for fol in reversed(folder):
        for fol in folder:
            key = fol[:fol.rindex(\"/\")]
            if key in response_obj:
                continue
            else:
                while key:
                    if key in response_obj:
                        break    
                    elif trie.has(key):
                        break
                    key = key[:key.rindex(\"/\")]
            
            if not key:
                response.append(fol)
                response_obj[fol] = \"\"
                
        del trie
        return response

class Solution:
    class TrieNode:
        def __init__(self):
            self.lookup = {}
            self.word = False
    
    class Trie:
        def __init__(self):
            self.root = Solution.TrieNode()
            
        def addPath(self,word):
            currNode = self.root
            for char in word:
                if char not in currNode.lookup:
                    currNode.lookup[char] = Solution.TrieNode()
                currNode = currNode.lookup[char]
            currNode.word = True
            
        def shortPath(self,word):
            currNode = self.root
            for index, char in enumerate(word):
                if currNode.word and char == '/':
                    return word[:index]
                currNode = currNode.lookup[char]
            
            return word
    
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = Solution.Trie()
        result = set()
        for path in folder:
            trie.addPath(path)
            
        for path in folder:
            result.add(trie.shortPath(path))
            
        return list(result)


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        class Trie:
            def __init__(self):
                self.child = {}
                self.is_word = False
            def add(self,word):
                curr = self
                for w in word:
                    if w not in curr.child:
                        curr.child[w] = Trie()
                    curr = curr.child[w]
                curr.is_word = True
            def get_val(self,word):
                curr = self
                ans = \"\"
                for w in word:
                    if w in curr.child:
                        ans += w
                        curr = curr.child[w]
                        if curr.is_word and \"/\" in curr.child:
                            return ans
                return ans
        def remove_dir(folders):
            trie = Trie()
            ans = set()
            for f in folders:
                trie.add(f)
            for f in folders:
                ans.add(trie.get_val(f))
            return list(ans)
        return remove_dir(folder)

class Trie:
    def __init__(self):
        self.root = {\"*\": \"*\"}

    def add(self, word):
        current = self.root
        for letter in word:
            if letter not in current:
                current[letter] = {}
            current = current[letter]
        current[\"*\"] = \"*\"

    def has(self, word):
        current = self.root
        for letter in word:
            if letter not in current:
                return False
            current = current[letter]

        return \"*\" in current

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = Trie()
        for fol in folder:
            trie.add(fol)
        
        response = list()
        response_obj = {}
        for fol in folder:
            key = fol[:fol.rindex(\"/\")]
            while key:
                if key in response_obj:
                    break    
                elif trie.has(key):
                    break
                key = key[:key.rindex(\"/\")]
            
            if not key:
                response.append(fol)
                response_obj[fol] = \"\"

        return response

from collections import deque

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False
        
class Trie:
    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, word):
        p = self.root
        for c in word:
            if c not in p.children:
                p.children[c] = TrieNode()
            p = p.children[c]
            
        p.is_word = True
        return p


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        if folder is None or not folder:
            return []
        
        trie = Trie()
        
        for f in folder:
            trie.insert(f)
            
        ret = []
        
        queue = deque([(trie.root, '')])
        
        while queue:
            p, acc = queue.popleft()
            
            if p.is_word:
                ret.append(acc)
                
            for letter in p.children:
                if p.is_word and letter == '/':
                    continue
                queue.append((p.children[letter], acc + letter))
                
        return ret

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        
        folder.sort(key = lambda x: len(x))
        res = []
        # while folder:
        #     e = folder.pop()
        #     for p in folder:
        #         if e.startswith(p) and e[len(p)] == '/':
        #                 e = ''   
        #                 break
        #     if e: res.append(e)
        # return res
    
        trie = defaultdict(dict)
        for t in folder:
            m = trie
            parent = False
            for c in t.split('/'):
                
                if c in m: m = m[c]
                else: 
                    m[c] = {}
                    m = m[c]
                if '$' in m: 
                    parent = True
                    break
            if not parent:
                m[\"$\"] = '$'
                res.append(t)
        return res
            

class Trie:
    def __init__(self):
        self.root = {\"*\": \"*\"}

    def add(self, word):
        current = self.root
        for letter in word:
            if letter not in current:
                current[letter] = {}
            current = current[letter]
        current[\"*\"] = \"*\"

    def has(self, word):
        current = self.root
        for letter in word:
            if letter not in current:
                return False
            current = current[letter]

        return \"*\" in current

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:        
        # folder = sorted(folder1, key=len) 
        trie = Trie()
        for fol in folder:
            trie.add(fol)
        
        response = list()
        response_obj = {}
        # for fol in reversed(folder):
        for fol in folder:
            key = fol[:fol.rindex(\"/\")]
            if key in response_obj:
                continue
            else:
                while key:
                    if key in response_obj:
                        break    
                    if trie.has(key):
                        break
                    key = key[:key.rindex(\"/\")]
            
            if not key:
                response.append(fol)
                response_obj[fol] = \"\"
                
        del trie
        return response

class Trie:
    def __init__(self):
        self.root = {\"*\": \"*\"}

    def add(self, word):
        current = self.root
        for letter in word:
            if letter not in current:
                current[letter] = {}
            current = current[letter]
        current[\"*\"] = \"*\"

    def has(self, word):
        current = self.root
        for letter in word:
            if letter not in current:
                return False
            current = current[letter]

        return \"*\" in current

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:        
        # folder = sorted(folder1, key=len) 
        trie = Trie()
        for fol in folder:
            trie.add(fol)
        
        response = list()
        # for fol in reversed(folder):
        for fol in folder:
            key = fol[:fol.rindex(\"/\")]
            while key:
                if trie.has(key):
                    break
                key = key[:key.rindex(\"/\")]
            
            if not key:
                response.append(fol)
                
        del trie
        return response

class Trie:
    def __init__(self):
        self.root = {\"*\": \"*\"}

    def add(self, word):
        current = self.root
        for letter in word:
            if letter not in current:
                current[letter] = {}
            current = current[letter]
        current[\"*\"] = \"*\"

    def has(self, word):
        current = self.root
        for letter in word:
            if letter not in current:
                return False
            current = current[letter]

        return \"*\" in current

class Solution:
    def removeSubfolders(self, folder1: List[str]) -> List[str]:        
        folder = sorted(folder1, key=len) 
        trie = Trie()
        for fol in folder:
            trie.add(fol)
        
        response = set()
        # for fol in reversed(folder):
        for fol in folder:
            key = fol[:fol.rindex(\"/\")]
            while key:
                if trie.has(key):
                    break
                key = key[:key.rindex(\"/\")]
            
            if not key:
                response.add(fol)
                
        del trie
        return response

class Solution:
    # 432 ms, 36.84%
    # def removeSubfolders(self, folder: List[str]) -> List[str]:
    #     folder.sort()
    #     l  = [folder[0]]
    #     p = folder[0]
    #     for f in folder[1:]:
    #         if not f.startswith(p + '/'):
    #             l.append(f)
    #             p = f
    #     return l
    
    
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        def insert(f):
            t = r
            for c in f:
                if c not in t.ch:
                    t.ch[c] = TrieNode()
                t = t.ch[c]
            t.ch['/'] = TrieNode()
            t = t.ch['/']
            t.d = True
        def search(f):
            t = r
            for c in f:
                t = t.ch[c]
                if t.d:
                    return False
            return True
        r = TrieNode()
        for f in folder:
            insert(f)
        l = []
        for f in folder:
            if search(f):
                l.append(f)
        return l
    
class TrieNode:
    def __init__(self):
        self.ch = {}
        self.d = False

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()
        # ans = [ folder[0]]
        # prev = folder[0] + '/'
        # for f in folder[1:]:
        #     if not f.startswith(prev):
        #         ans.append(f)
        #         prev = f+'/'
        # return ans
        
        #using set
        ans = []
        seen = set(folder)
        for i in folder:
            path = i
            while path:
                path = path[:path.rfind('/')]
                if path in seen:
                    break
            else:
                ans.append(i)
        return (ans)

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        seen = set()
        folder.sort(key=len)
        
        for fd in folder:
            for i in range(2, len(fd)):
                if fd[i] == \"/\":
                    if fd[:i] in seen:
                        break
            else:
                seen.add(fd)
                
        return list(seen)
                
                        
                        
                    
                
        

def is_parent(f1, f2):
            f1 = f1.split('/')
            f2 = f2.split('/')
            if len(f1) > len(f2): 
                return False
            for a, b in zip(f1, f2):
                if a!=b:
                    return False
            return True
    
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder = sorted(folder)
        ans = []
        
            
        for f in folder:
            if not ans or not is_parent(ans[-1], f):
                ans.append(f)                
        return ans


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()
        ans = [ folder[0]]
        prev = folder[0] + '/'
        for f in folder[1:]:
            if not f.startswith(prev):
                ans.append(f)
                prev = f+'/'
        return ans

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort(key = lambda f:len(f))
        
        seen = set()
        
        for f in folder:
            for i in range(2, len(f)):
                if f[i] == '/' and f[: i] in seen:
                    break
            else:
                seen.add(f)
                    
        return list(seen)

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        if not folder:
            return None 
        folder.sort(key = lambda x: len(x))
        seen = set()
        for fold in folder:
            for i in range(2, len(fold)):
                if fold[i] == '/' and fold[:i] in seen:
                    break 
            else:
                seen.add(fold)
        return list(seen)

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder = sorted(folder,key = lambda e: len(e))
        res = set()
        for f in folder:
            flag = True
            for i in range(2, len(f)):
                if f[i] == '/' and f[:i] in res:
                    flag = False
                    break
            if flag:
                res.add(f)
        return list(res)


class TrieNode:
    def __init__(self):
        self.d = {}
        self.w = False
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder = sorted(folder)
        root = TrieNode()
        res = []
        for file in folder:
            p = root
            end = False
            for w in file.split('/'):
                if p.w:
                    end = True
                    break
                if w not in p.d:
                    p.d[w] = TrieNode()
                p = p.d[w]
            if end:
                continue
            p.w = True
            res.append(file)
        return res


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        '''
        Build trie from the folders, whenever a folder ends, just drop all of its children (subfolders) in the trie.
        '''
        trie = {}
        for f in folder:
            path = f.split('/')[1:]
            cur = trie
            for idx, p in enumerate(path):
                if idx == len(path) - 1:
                    # this is the ending folder
                    cur[p] = '#'
                else:
                    if p in cur:
                        if cur[p] != '#':
                            cur = cur[p]
                        else:
                            # we see an ending folder, stop adding subfolders to it
                            break
                    else:
                        cur[p] = {}
                        cur = cur[p]
        
        # do a DFS of the trie to get the answers
        ans = []
        def dfs(cur_dir, path):
            if cur_dir == '#':
                ans.append('/' + '/'.join(path))
                return
            for k in cur_dir:
                dfs(cur_dir[k], path + [k])
            return
        dfs(trie, [])
        return ans
            


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        '''
        Build trie from the folders, whenever a folder ends, just drop all of its children (subfolders) in the trie.
        Time O(N) to build the trie and do DFS
        Space O(N) for the trie
        '''
        trie = {}
        for f in folder:
            path = f.split('/')[1:]
            cur = trie
            for idx, p in enumerate(path):
                if idx == len(path) - 1:
                    # this is the ending folder
                    cur[p] = '#'
                else:
                    if p in cur:
                        if cur[p] != '#':
                            cur = cur[p]
                        else:
                            # we see an ending folder, stop adding subfolders to it
                            break
                    else:
                        cur[p] = {}
                        cur = cur[p]
        
        # do a DFS of the trie to get the answers
        ans = []
        def dfs(cur_dir, path):
            if cur_dir == '#':
                ans.append(path)
                return
            for k in cur_dir:
                dfs(cur_dir[k], path + '/' + k)
            return
        dfs(trie, '')
        return ans
            


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        '''
        Build trie from the folders, whenever a folder ends, just drop all of its children (subfolders) in the trie.
        Time O(N) to build the trie and do DFS
        Space O(N) for the trie
        '''
        trie = {}
        for f in folder:
            path = f.split('/')[1:]
            cur = trie
            for idx, p in enumerate(path):
                if idx < len(path) - 1:
                    if p in cur:
                        if cur[p] != '#':
                            cur = cur[p]
                        else:
                            # we see an ending folder, stop adding subfolders to it
                            break
                    else:
                        cur[p] = {}
                        cur = cur[p]
                else:
                    # this is the ending folder
                    cur[p] = '#'
                    
        
        # do a DFS of the trie to get the answers
        ans = []
        def dfs(cur_dir, path):
            if cur_dir == '#':
                ans.append(path)
                return
            for k in cur_dir:
                dfs(cur_dir[k], path + '/' + k)
            return
        dfs(trie, '')
        return ans
            


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        '''
        Build trie from the folders, whenever a folder ends, just drop all of its children (subfolders) in the trie.
        Time O(N) to build the trie and do DFS
        Space O(N) for the trie
        '''
        trie = {}
        for f in folder:
            path = f.split('/')[1:]
            cur = trie
            for idx, p in enumerate(path):
                if idx == len(path) - 1:
                    # this is the ending folder
                    cur[p] = '#'
                else:
                    if p in cur:
                        if cur[p] != '#':
                            cur = cur[p]
                        else:
                            # we see an ending folder, stop adding subfolders to it
                            break
                    else:
                        cur[p] = {}
                        cur = cur[p]
        
        # do a DFS of the trie to get the answers
        ans = []
        def dfs(cur_dir, path):
            if cur_dir == '#':
                ans.append('/' + '/'.join(path))
                return
            for k in cur_dir:
                dfs(cur_dir[k], path + [k])
            return
        dfs(trie, [])
        return ans
            


class Solution:
    def removeSubfolders(self, folders: List[str]) -> List[str]:
        folders.sort()
        output = []
        parent = ' '
        for folder in folders:
            if not folder.startswith(parent):
                output.append(folder)
                parent = folder+'/'
        return output

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        s_f = sorted(folder)
        root = {}
        result = []
        for i in range(len(s_f)):
            path = s_f[i]
            p_arr = path.split(\"/\")[1:]
            cur = root
            for j in range(len(p_arr)):
                if -1 in cur:
                    break
                #abc
                if p_arr[j] not in cur:
                    cur[p_arr[j]] = {}
                cur = cur[p_arr[j]]
                if j == len(p_arr) - 1:
                    cur[-1] = i
                    result.append(path)
        return result
            
            

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        self.trie = {}
        
        for path in folder:
            node = self.trie
            for c in path.split('/'):
                if c not in node:
                    node[c] = {}
                node = node[c]
            node['*'] = True
            
        res = []
        node = self.trie
        stack = [(node, [])]
        while len(stack):
            node, prefix = stack.pop()
            if '*' in node and node['*']:
                res.append('/'.join(prefix))
            else:
                for k, v in list(node.items()):
                    stack.append((v, prefix+[k]))
                    
        return res


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        res = []
        folder.sort(key = lambda x: len(x))
        seen = set()
        for f in folder:
            if not any(f[i] == '/' and f[:i] in seen for i in range(2, len(f))):
                seen.add(f)
        return list(seen)


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()
        seen = set()
        for path in folder:
            if not any(path[i] == '/' and path[:i] in seen for i in range(2, len(path))):
                seen.add(path)
        return seen
    
                
# Trie
#         trie = {}
#         for path in folder:
#             curr = trie
#             for f in path.split('/'):
#                 if f in curr:
#                     curr = curr[f]
#                 else:
#                     curr[f] = {}
#                     curr = curr[f]
#             curr[None] = None
        
#         res = []
#         for path in folder:
#             curr = trie
#             issub = False
#             for f in path.split('/'):
#                 if None in curr: 
#                     issub = True
#                 else:
#                     curr = curr[f]
#             if not issub:
#                 res.append(path)
                
#         return res
            
            
            
            
        
        
        
                
                
            
            
            


from collections import defaultdict
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        Trie = lambda: defaultdict(Trie)
        trie = Trie()

        for f in folder:
            t = trie
            for c in f[1:].split('/'):
                t = t[c]
            t[None] = None

        res = []

        def dfs(t, path=[]):
            if None in t:
                res.append('/' + '/'.join(path))
                return

            for c, nt in list(t.items()):
                path.append(c)
                dfs(nt, path)
                path.pop()

        dfs(trie)

        return res



class TreeNode:
    
    def __init__(self, val):
        self.val = val
        self.folders = {}
        self.exist = False
        
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        
        self.tree = TreeNode('.')
        for this_folder in folder:
            path = this_folder.split('/')[1:]
            pointer = self.tree
            for name in path:
                if pointer.exist:
                    break
                if name not in pointer.folders:
                    pointer.folders[name] = TreeNode(name)
                pointer = pointer.folders[name]
            pointer.exist = True
        
        ret = []
        
        # print(self.tree)
        # print(self.tree.folders)
        # print(self.tree.folders['a'].folders)
        # print(self.tree.folders['a'].exist)
        
        def buildPath(curr, path):
            if curr is None:
                return
            if curr.exist:
                ret.append(path)
                return
            for sub_name, sub in curr.folders.items():
                buildPath(sub, path + '/' + sub_name)
        
        buildPath(self.tree, '')
        return ret

class TreeNode:
    def __init__(self):
        self.val = '/'
        self.children = {}
        self.isleaf = False
        
    def insert(self, val):
        if not val:
            self.isleaf = True
            return
        if val[0] in self.children:
            self.children[val[0]].insert(val[1:])
            return
        newnode = TreeNode()
        newnode.val = val[0]
        self.children[val[0]] = newnode
        newnode.insert(val[1:])
    
    def isparent(self, val):
        if val and val[0] in self.children:
            return self.children[val[0]].isleaf or self.children[val[0]].isparent(val[1:])
        return False
    
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder = sorted(folder)
        ans = []
        
        fs = TreeNode()
        for f in folder:
            has_parent = fs.isparent(f.split('/'))
            if not has_parent:
                ans.append(f)
                fs.insert(f.split('/'))
        return ans


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        if not folder:
            return []
        
        trie = {}
        for folderPath in folder:
            paths = folderPath.split(\"/\")
            
            node  = trie
            parent = None
            parentExists = False
            for path in paths[:-1]:
                if \"$\" in node:
                    parentExists = True
                    break
                
                if path not in node:
                    node[path] = {}
                
                parent = node
                node = node[path]
            
            if parentExists or \"$\" in node: continue
            
            #print(node, paths[-1])
            node[paths[-1]] = {\"$\": {}}
        
        #print(trie)
        self.res = []
        self.dfs(trie, [])
        return self.res
    
    def dfs(self, node, pathList):
        for key in node:
            if key == \"$\":
                self.res.append(\"/\".join(pathList))
            else:
                pathList.append(key)
                self.dfs(node[key], pathList)
                pathList.pop()
        
            
    
            
                
            
        
        

class TrieNode:
    def __init__(self, val):
        self.val = val
        self.next = {}
        self.path = None

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = TrieNode(\"\")
        
        for path in folder:
            node = trie
            names = path.split(\"/\")[1:]
            
            for name in names:
                if node.path:
                    break
                if name not in node.next:
                    node.next[name] = TrieNode(name)
                node = node.next[name]
            else:
                node.path = path
            
        res = []
        
        self.dfs(trie, res)
                
        return res
    
    def dfs(self, node, res):
        if node.path:
            res.append(node.path)
            return
        
        for child in node.next:
            self.dfs(node.next[child], res)
                    
# time: O(n*m)
# space: O(n*m)

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        
        
        folders_set = set(folder)
        res = []
        # print(folders, \"/a\" in folders)
        
        
        for folder_and_subfolder in folder:
            
            folders = folder_and_subfolder.split('/')[1:]
            print(folders)
            
            i = 0 
            subfolder = \"/\"
            flag = False
            while i < len(folders):
                
                subfolder = subfolder + str(folders[i]) 
                # print((subfolder), str(subfolder) in folders_set)
                if subfolder in folders_set:
                    flag = True
                    res.append(subfolder)
                    break
                subfolder += \"/\"
                
                i+=1
            if not flag:
                res.append(subfolder)
                
            
        return list(set(res))
                
            
            

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        # time O(mn+nlogn); space O(m)
        res = []
        for f in sorted(folder):
            if not res or not f.startswith(res[-1] + '/'):
                res.append(f)
        return res

class TreeNode:
    def __init__(self, val='/'):
        self.val = val
        self.children = {}
        self.isleaf = False
        
    def insert(self, val):
        if not val:
            self.isleaf = True
            return
        if val[0] in self.children:
            self.children[val[0]].insert(val[1:])
            return
        newnode = TreeNode(val=val[0])
        self.children[val[0]] = newnode
        newnode.insert(val[1:])
    
    def isparent(self, val):
        if val and val[0] in self.children:
            return self.children[val[0]].isleaf or self.children[val[0]].isparent(val[1:])
        return False
    
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder = sorted(folder)
        ans = []
        fs = TreeNode()
        for f in folder:
            f_splitted = f.split('/')
            has_parent = fs.isparent(f_splitted)
            if not has_parent:
                ans.append(f)
                fs.insert(f_splitted)
        return ans


class TreeNode:
    def __init__(self):
        self.val = '/'
        self.children = []
        self.isleaf = False
        
    def insert(self, val):
        if not val:
            self.isleaf = True
            return
        for child in self.children:
            if child.val == val[0]:
                child.insert(val[1:])
                return
        newnode = TreeNode()
        newnode.val = val[0]
        self.children.append(newnode)
        newnode.insert(val[1:])
    
    def isparent(self, val):
        for child in self.children:
            if child.val == val[0] :
                if child.isleaf:
                    return True
                return child.isparent(val[1:])
        return False
                    
def is_parent(f1, f2):
            f1 = f1.split('/')
            f2 = f2.split('/')
            if len(f1) > len(f2): 
                return False
            return all([ a==b for a, b in zip(f1, f2)])
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder = sorted(folder)
        ans = []
        
        fs = TreeNode()
        for f in folder:
            has_parent = fs.isparent(f.split('/'))
            if not has_parent:
                ans.append(f)
                fs.insert(f.split('/'))
        return ans


class Node:
    def __init__(self):
        self.children = {}
        self.is_word = False
    

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        if folder is None or not folder:
            return []
        
        root = self._create_tree(folder)
        
        ret = []
        self._helper(root, [], ret)
        return ret
        
    def _helper(self, p, acc, ret):
        if p.is_word:
            ret.append('/' + '/'.join(acc))
            return
        
        for c in p.children:
            acc.append(c)
            
            self._helper(p.children[c], acc, ret)
            
            acc.pop()
        
        
    def _create_tree(self, folder):
        root = Node()
        
        for f in folder:
            t = f.split('/')
            p = root
            
            for i in range(1, len(t)):
                if p.is_word:
                    break
                    
                name = t[i]
                if name not in p.children:
                    p.children[name] = Node()
                p = p.children[name]
            p.is_word = True
            p.children = {}
        
        return root

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = {}
        tokens = {path: path.split('/') for path in folder}
        for path in folder:
            curr = trie
            for token in tokens[path]:
                if '#' in curr:
                    break
                if token not in curr:
                    curr[token] = {}
                curr = curr[token]
            curr['#'] = True
 
        paths = set(folder)
        for path in folder:
            curr = trie
            for token in tokens[path]:
                if '#' in curr:
                    paths.remove(path)
                    break
                curr = curr[token]    
        return list(paths) 
                


class Trie():
    def __init__(self):
        self.children = {}
        
    def put(self, s):
        s = s.split(\"/\")
        check = self.children
        for c in s[1:]:
            if c not in check:
                check[c] = {}
            check = check[c]
        check[-1] = True
    
    def find(self, s):
        s = s.split(\"/\")
        check = self.children
        for c in s[1:]:
            if c not in check:
                return False
            check = check[c]
        return -1 in check
            
    

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        ret = []
        def dfs(children, build):
            if -1 in children:
                ret.append(\"/\"+\"/\".join(build))
                return
            for c in children:
                dfs(children[c], build+[c])
                
        trie = Trie()
        
        for f in folder:
            #print(f)
            trie.put(f)
        #print(trie.children)
        check = trie.children
        stack = []
        dfs(check, [])
        return ret
                
        \"\"\"
        d = {}
        ret = []
        folder.sort()
        for f in folder:
            fl = f.split(\"/\")
            for i in range(1, len(fl)):
                tup_h = tuple(fl[1:i+1])
                if tup_h in d:
                    break
                elif i == len(fl)-1:
                    d[tup_h] = f
                    ret.append(f)
        return ret
        \"\"\"

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = {}
        for path in folder:
            curr = trie
            for f in path.split('/'):
                if f in curr:
                    curr = curr[f]
                else:
                    curr[f] = {}
                    curr = curr[f]
            curr[None] = None
        
        res = []
        for path in folder:
            curr = trie
            issub = False
            for f in path.split('/'):
                if None in curr: 
                    issub = True
                else:
                    curr = curr[f]
            if not issub:
                res.append(path)
                
        return res
            
            
            
            
        
        
        
                
                
            
            
            


# trie (dictionary tree)
# time complexity: O(NM), N = len(folder), M = len(folder[0])
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        # 1st step
        # build the dictionary tree
        trie = dict()
        trie[''] = [0,dict()]
        for f in folder:
            curr = trie
            prev = None
            for c in f.split('/'):
                if c not in curr:
                    curr[c] = [0,dict()]
                #print(f'c=|{c}|')
                prev = curr
                curr = curr[c][1]
            prev[c][0] = 1
        
        
        # 2nd step
        # traverse the dictionary tree in pre order, find the highest node with 1 of each subtree
        clean = []
        stack = [([''],trie[''])] # path, node
        while stack:
            p,(isPath,d) = stack.pop()
            if isPath == 0:
                for c in d:
                    stack.append((p+[c], d[c]))
            else:
                clean.append('/'.join(p))
        return clean
            


from pprint import pprint as pp
class Solution:
    def removeSubfolders2(self, folder: List[str]) -> List[str]:
        folder.sort(key=len)
        st = set()
        for f in folder:
            for i in range(len(f)):
                if f[i] == \"/\" and i > 0:
                    if f[:i] in st:
                        break
            else:
                st.add(f)
        return list(st)
    
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = {}
        def insert(t, word):
            for w in word:
                if w not in t:
                    t[w] = {}
                t = t[w]
            t['#'] = word
        for f in folder:
            word = f.split('/')[1:]
            insert(trie, word)
        def dfs(t):
            if '#' in t:
                return ['/' + '/'.join(t['#'])]
            res = []
            for w in t:
                res += dfs(t[w])
            return res
        return dfs(trie)

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = {}
        for path in folder:
            tokens = path.split('/')
            curr = trie
            for token in tokens:
                if token not in curr:
                    curr[token] = {}
                curr = curr[token]
            curr['#'] = True
        
        paths = set(folder)
        for path in folder:
            tokens = path.split('/')
            curr = trie
            for token in tokens:
                if '#' in curr:
                    paths.remove(path)
                    break
                curr = curr[token]    
        return list(paths) 
                


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        if not folder:
            return []
        folder.sort()
        result = [folder[0]]
        for f in folder:
            if f != result[-1] and not f.startswith(result[-1] + \"/\"):
                result.append(f)
        return result
                
            
            
        

class Node:
    def __init__(self, v):
        self.v = v
        self.children = {}
    
    def __repr__(self):
        return f'Node({self.v} {self.children.keys()})'

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = Node('')
        for f in folder:
            self.add_to_trie(trie, f)
        
        return ['/' + '/'.join(i) for i in self.dfs(trie)]
    
    def dfs(self, cur):
        if not cur.children:
            return [[]]
        res = []
        for child, child_node in cur.children.items():
            for sub_res in self.dfs(child_node):
                res.append([child] + sub_res)
        return res
        
    def add_to_trie(self, trie, f):
        if not f:
            return

        sub_folders = f.split('/')[1:]
        if sub_folders[0] in trie.children:
            cur = trie
            for i, sub_folder in enumerate(sub_folders):
                if sub_folder not in cur.children and not cur.children:
                    return
                elif sub_folder not in cur.children:
                    self.add_subs_to_trie(cur, i, sub_folders)
                    return
                else:
                    cur = cur.children[sub_folder]
            if cur.children:
                cur.children = {}
        else:
            self.add_subs_to_trie(trie, 0, sub_folders)
        
    def add_subs_to_trie(self, trie, ix, sub_folders):
        cur = trie
        for i in range(ix, len(sub_folders)):
            sub_folder = sub_folders[i]
            cur.children[sub_folder] = Node(sub_folder)
            cur = cur.children[sub_folder]

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        
        if len(folder) == 1:
            return folder
        
        #def is_subfolder(folder1, folder2):
        #    s_f1 = folder1.split('/')
        #    s_f2 = folder2.split('/')
        #    
        #    if len(s_f1) < len(s_f2):
        #        i = 0
        #        while i < len(s_f1):
        #            if s_f1[i] == s_f2[i]:
        #                i += 1
        #            else:
        #                return False
        #        return True
                    
        
        
        folder.sort()
        #for i,j in enumerate(folder):
        i = 0
        while i < len(folder) - 1:
                #
                #if is_subfolder(folder[i], folder[i+1]):
                #if len(folder[i+1]) > len(folder[i]):
            #if folder[i+1].startswith('{}/'.format(folder[i])):
            if folder[i+1].startswith(folder[i]+'/'):
            #if '{}/'.format(folder[i]) == folder[i+1][:(len(folder[i])+1)]:
                folder.pop(i+1)
            else:
                i+=1
            
        return folder    


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        tmp = '*'
        res = []
        for elem in sorted(folder):
            if not elem.startswith(tmp):
                tmp = elem + '/'
                res.append(elem)
        return res


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        
        if len(folder) == 1:
            return folder
        
        #def is_subfolder(folder1, folder2):
        #    s_f1 = folder1.split('/')
        #    s_f2 = folder2.split('/')
        #    
        #    if len(s_f1) < len(s_f2):
        #        i = 0
        #        while i < len(s_f1):
        #            if s_f1[i] == s_f2[i]:
        #                i += 1
        #            else:
        #                return False
        #        return True
                    
        
        
        folder.sort()
        #for i,j in enumerate(folder):
        i = 0
        while i < len(folder) - 1:
                #
                #if is_subfolder(folder[i], folder[i+1]):
                #if len(folder[i+1]) > len(folder[i]):
            if folder[i+1].startswith('{}/'.format(folder[i])):
            #if '{}/'.format(folder[i]) == folder[i+1][:(len(folder[i])+1)]:
                folder.pop(i+1)
            else:
                i+=1
            
        return folder    


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        res = set()
        folder.sort(key = len)
        for fold in folder:
            flag = 0
            for i in range(2, len(fold)):
                if fold[i] == '/':
                    if fold[:i] in res:
                        flag = 1
                        break
            if flag == 0: res.add(fold)
        return list(res)

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        
        if len(folder) == 1:
            return folder
        
        #def is_subfolder(folder1, folder2):
        #    s_f1 = folder1.split('/')
        #    s_f2 = folder2.split('/')
        #    
        #    if len(s_f1) < len(s_f2):
        #        i = 0
        #        while i < len(s_f1):
        #            if s_f1[i] == s_f2[i]:
        #                i += 1
        #            else:
        #                return False
        #        return True
                    
        
        
        folder.sort()
        #for i,j in enumerate(folder):
        i = 0
        while i < len(folder) - 1:
                #
                #if is_subfolder(folder[i], folder[i+1]):
                #if len(folder[i+1]) > len(folder[i]):
                #if folder[i+1].startswith('{}/'.format(folder[i])):
            if '{}/'.format(folder[i]) == folder[i+1][:(len(folder[i])+1)]:
                folder.pop(i+1)
            else:
                i+=1
            
        return folder    


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
      dicts = {}
      res = []
      folder.sort(key = lambda x: len(x))
      for fo in folder:
        candidates = []
        for i in range(len(fo)):
          if fo[i] == '/':
            candidates.append(i)
        candidates = candidates[1:]
        candidates.append(len(fo))
        add = True
        for can in candidates:
          if fo[:can] in dicts:
            add = False
            break
        if add: 
          res.append(fo)
          dicts[fo] = 1
      return res

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEnd = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.isEnd = True  
    
    def get_smallest(self):
        def dfs(path, node):
            if node.isEnd:
                answer.append('/' + '/'.join(path))
                return
            for char in node.children:
                dfs(path + [char], node.children[char])
        
        answer = []
        dfs([], self.root)
        return answer


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = Trie()
        for f in folder:
            f = f.split('/')[1:]
            trie.insert(f)
        
        return trie.get_smallest()

class Trie:
    def __init__(self):
        self.chi = collections.defaultdict(Trie)
        self.ise = False
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        root = Trie()
        sta = []
        for x in sorted(folder):
            node = root
            tmp = x[1:].split('/')
            for y in tmp:
                node = node.chi[y]
                if node.ise:
                    break
            else:
                node.ise = True
                sta.append(x)
        return sta

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        res = []
        for f in sorted(folder):
            if not res or not f.startswith(res[-1] + '/'):
                res.append(f)
        return res
        # res = []
        # folder.sort(key = lambda x: len(x))
        # seen = set()
        # for f in folder:
        #     if not any(f[i] == '/' and f[:i] in seen for i in range(2, len(f))):
        #         seen.add(f)
        # return list(seen)


class Trie:
    def __init__(self):
        self.child = {}
        self.isLast = False
        
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        if not folder: return []
        root = Trie()
        
        # add
        for sf in folder:
            lists = sf[1:].split('/')
            if lists: self.add(root, lists) # ['a'], ['a','b'], ['c','d'], ['c','d','e'], ['c','f']
        
        # retrieve
        res=[]
        self.dfs(root, [], res)
        return res
        
    def dfs(self, root, temp, res):
        cur = root
        if cur.isLast: 
            res+='/'+'/'.join(temp),
            return 
        for ch in cur.child:
            self.dfs(cur.child[ch], temp+[ch], res)
            
            
            
        
    def add(self, root, lists):        
            
        cur = root
        for elem in lists:            
            if elem not in cur.child: cur.child[elem]=Trie()
            cur = cur.child[elem]
        cur.isLast = True
        


class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
        
class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, pathes):
        node = self.root
        for p in pathes:
            if p not in node.children:
                node.children[p] = TrieNode()
            node = node.children[p]
        node.is_end = True
        
    def find(self):
        ans = []
        def dfs(pathes, node):
            if node.is_end:
                ans.append('/' + '/'.join(pathes))
                return 
            for p in node.children:
                dfs(pathes + [p], node.children[p])
        dfs([], self.root)
        return ans
            
            
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = Trie()
        for f in folder:
            trie.insert(f.split('/')[1:])
        return trie.find()
            


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()
        res = []
        pfix = set()
        removed = set()
        
        for f in folder:
            valid = f.split('/')
            for i in range(0, len(valid)):
                target = '/'.join(valid[0: i + 1])
                if target in pfix:
                    removed.add(f)
            pfix.add(f)
        
        return set(folder) - set(removed)


class Directory:
    
    def __init__(self, name=\"\"):
        self.name = name
        self.subDirectories = {}
        self.flg=False

class Solution:
    
    def __init__(self):
        self.root = Directory()
        
    def generate(self, directory):
        if directory.flg:
            return [[directory.name]]
        res = []
        for k in directory.subDirectories.keys():
            res += self.generate(directory.subDirectories[k])
        for r in res:
            r.append(directory.name)
        return res
        
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        for f in folder:
            directories = re.split('/', f)[1:]
            cur = self.root
            for i, d in enumerate(directories):
                if cur.flg:
                    break
                if d not in cur.subDirectories.keys():
                    cur.subDirectories[d] = Directory(d)
                cur = cur.subDirectories[d]
                if i == len(directories) - 1:
                    cur.flg = True
        
        ans = self.generate(self.root)
        return ['/'.join(a[::-1]) for a in ans]
        

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEnd = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        curr_node = self.root
        
        for ch in word:
            if ch not in curr_node.children:
                curr_node.children[ch] = TrieNode()
            curr_node = curr_node.children[ch]
        curr_node.isEnd = True
    
    def find(self):
        def dfs(node, file, result):
            if node.isEnd:
                result.append(\"/\" + \"/\".join(file))
                return
            
            for ch in node.children:
                dfs(node.children[ch], file + [ch], result)
        result = []
        dfs(self.root, [], result)
        return result
    
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = Trie()
        
        for file in folder:
            file = file.split(\"/\")[1:]
            trie.insert(file)
        return trie.find()
        

# Time & space: O(n * m), where n = folder.length, m = average size of the strings in folder.
class TrieNode:
    def __init__(self):
        self.children = dict() 
        self.path = None 
        
class Solution:
    def __init__(self):
        self.root = TrieNode() 
        
    def removeSubfolders(self, folder: List[str]) -> List[str]:        
        for directory in folder:
            curr = self.root
            for f in directory.split('/')[1:]:
                if f not in curr.children:
                    curr.children[f] = TrieNode()
                curr = curr.children[f]    
            curr.path = directory    
        
        def trie_search(node, res): #dfs
            if node.path:
                res.append(node.path)
                return res
            for nbr in node.children:  
                res = trie_search(node.children[nbr], res)
            return res    
        
        return trie_search(self.root, [])

# # Sort the folders;
# # For each folder check if the followings are child folders; if yes, ignore; otherwise, count it in.
# # Time: O(n * m * log(n)), space: O(1)(excluding space cost of sorting part), where n = folder.length, m = average size of the strings in folder.
# class Solution:
#     def removeSubfolders(self, folder: List[str]) -> List[str]:
#             ans = []
#             for f in sorted(folder):
#                 if not ans or not f.startswith(ans[-1] + '/'):\t#  need '/' to ensure a parent.
#                     ans.append(f)
#             return ans


import collections
class Trienode:
    def __init__(self):
        self.child = collections.defaultdict(Trienode)
        self.isword = False
class trie:
    def __init__(self):
        self.res = Trienode()
    def insert(self,word):
        cur = self.res
        for i in word:
            cur = cur.child[i]
        cur.isword =True
    def find(self):
        self.stack =[]
        def dfs(node,tmp):
            for item in node.child.keys():
                if node.child[item].isword:
                    self.stack.extend([tmp+\"/\"+item])
                else:
                    dfs(node.child[item],tmp+\"/\"+item)
        dfs(self.res,\"\")
        return self.stack 
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        newres = trie()
        for item in folder:
            item = item.split(\"/\")[1:]
            newres.insert(item)
        
        return [item for item in newres.find()]

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        t = Trie()
        
        for i in folder:
            t.insert(i.split(\"/\")[1:])
            
        return t.getFolders()
        
class TrieNode:
    def __init__(self, val=None):
        self.val = val
        self.children = {}
        self.isEnd = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, s):
        curr = self.root
        for c in s:
            if c not in curr.children:
                curr.children[c] = TrieNode(c)
            curr = curr.children[c]
        curr.isEnd = True

    def getFolders(self):
        result = []
        
        def helper(node, path):
            if node.isEnd:
                result.append(path[:-1])
            else:
                for i in node.children:
                    helper(node.children[i],path + node.children[i].val + \"/\")

        helper(self.root, \"/\")
        
        return result

class Node:
    def __init__(self):
        self.child = collections.defaultdict(Node)
        self.is_last = False
class Trie:
    def __init__(self):
        self.root = Node()
    def insert(self, word):
        node = self.root
        for c in word:
            node = node.child[c]
        node.is_last = True
    def find(self):
        ret = []
        
        def dfs(node, tmp):
            if node.is_last:
                ret.append(\"/\".join(tmp))
                return
            for char, nxt_node in node.child.items():
                dfs(nxt_node, tmp+[char])
        dfs(self.root, [])
        return ret
        
    
    
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()
        t = Trie()
        for f in folder:
            t.insert(f.split(\"/\"))
        return t.find()

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        x = sorted(folder)
        res = [x[0]]
        for i in range(1, len(x)):
            if x[i].startswith(res[-1]) and (x[i][len(res[-1])] == '/'):
                continue
            res.append(x[i])
        return res


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        n = len(folder)
        folder = sorted(folder)
        first = folder[0]
        ans = set()
        # print((first.split('/')))
        ans.add(folder[0])
        for i in range(1,n):
            flag = True
            second = folder[i]
            # print(first,second)
            first1 = first.split('/')
            second1 = second.split('/')
            for j in range(len(first1)):
                if first1[j] != second1[j]:
                    ans.add(second)
                    first = second
                    flag = False
                    break
            
            # if flag:
            #     ans.add(first)
            
#         if not flag:
#             ans.add(folder[n-1])
        
        return list(ans)
                


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort(key=len)
        res = []
        seen = set()
        for path in folder:
            tmp = []
            for d in path.split('/')[1:]:
                tmp.append(d)
                if '/'.join(tmp) in seen: break
            else:
                seen.add('/'.join(tmp))
                res.append(path)
        return res

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = {}
        tokens = {path: path.split('/') for path in folder}
        for path in folder:
            curr = trie
            for token in tokens[path]:
                if token not in curr:
                    curr[token] = {}
                curr = curr[token]
            curr['#'] = True
 
        paths = set(folder)
        for path in folder:
            curr = trie
            for token in tokens[path]:
                if '#' in curr:
                    paths.remove(path)
                    break
                curr = curr[token]    
        return list(paths) 
                


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        if len(folder) == 1:
            return folder
        
        trie = {}
        for p in folder:
            node = trie
            p = p.split('/')
            for e in p:
                node = node.setdefault(e, {}) 
            node[\"#\"] = \"#\" #end
        
        restults = []
        self.dfs(trie, [], restults )
        return restults
            
        
    def dfs(self, trie, res, results):
        
        if '#' in trie:
            results.append('/'.join(res)) 
            return
               
        for e in trie:
            self.dfs(trie[e], res + [e], results)
            
            
        
        
            
            
            
        
        
            
            
        

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        s = sorted(folder)
        fs = []
        while s:
            fs.append(s[0])
            s.pop(0)
            while s and self.is_subfolder(fs[-1], s[0]):
                s.pop(0)
        return fs
    def is_subfolder(self, x,y):
        x = x.split('/')
        y = y.split('/')
        if len(x) >= len(y):
            return False
        for i, c in enumerate(x):
            if c != y[i]:
                return False
        return True

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        if len(folder) == 1:
            return folder
        
        trie = {}
        
        for p in folder:
            node = trie
            p = p.split('/')
            for e in p:
                node = node.setdefault(e, {}) 
            node[\"#\"] = \"#\" #end
        
        restults = []
        self.dfs(trie, [], restults )
        return restults
            
        
    def dfs(self, trie, res, results):
        
        if '#' in trie:
            results.append('/'.join(res)) 
            return
            
            
        for e in trie:
            res.append(e) 
            self.dfs(trie[e], res, results)
            res.pop()
            
        
        
            
            
            
        
        
            
            
        

import collections
class TrieNode:
    def __init__(self):
        self.child = collections.defaultdict(TrieNode)
        self.isword = False
        
class trie:
    def __init__(self):
        self.res = TrieNode()
    def insert(self,word):
        cur = self.res
        for i in word:
            #rint(i)
            cur = cur.child[i]
        cur.isword=True
        
    def find(self):
        def dfs(node,stack,tmp):
            print(node.child.keys())
            if node.isword:
                stack.append(tmp)
                return 
            for item in node.child.keys():
                print(item)
                dfs(node.child[item],stack,tmp+\"/\"+item)
        stack =[]
        cur = self.res
        dfs(cur,stack,\"\")
        return stack
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        res=trie()
        for item in folder:
            #print(item.split(\"/\")[1:])
            res.insert(item.split(\"/\")[1:])
        return res.find()

# class Solution:
#    def removeSubfolders(self, folder: List[str]) -> List[str]:
#         # Brute Force => TLE
#         # Time: O(n^2)
#         # Space: O(1)
#         def isSublist(shorter_path: List[str], longer_path: List[str]) -> bool:
#             if len(shorter_path) > len(longer_path):
#                 return False
#             for i in range(len(shorter_path)):
#                 if shorter_path[i] != longer_path[i]:
#                     return False
#             return True
#         res = []
#         n = len(folder)
#         for i in range(n):
#             is_subfolder = False
#             longer_path = folder[i].split('/')
#             for j in range(n):
#                 if j != i:
#                     shorter_path = folder[j].split('/')
#                     if isSublist(shorter_path, longer_path):
#                         is_subfolder = True
#                         break
#             if not is_subfolder:
#                 res.append(folder[i])
#         return res
#         # Sort alphabetically + Stack
#         # Time: O(nlogn)
#         # Space: O(1)
#         folder.sort()
#         stack = [folder[0]]
#         n = len(folder)
#         i = 1
#         while i < n:
#             shorter_path = stack[-1].split('/')
#             longer_path = folder[i].split('/')
#             if not isSublist(shorter_path, longer_path):
#                 stack.append(folder[i])
#             i += 1
#         return stack

# Trie
# Time: O(n)
# Space: O(n)
class Node:
    def __init__(self):
        self.children = {}
        self.isLeaf = False
        
class Trie:
    def __init__(self):
        self.root = Node()
        
    def insert(self, path: List[str]) -> None:
        node = self.root
        for directory in path:
            if directory not in node.children:
                node.children[directory] = Node()
            node = node.children[directory]
        node.isLeaf = True
        
    def search(self, path: List[str]) -> bool:
        node = self.root
        for directory in path:
            if directory not in node.children:
                return False
            node = node.children[directory]
        return node.isLeaf
    
    def startWith(self, path: List[str]) -> bool:
        node = self.root
        for directory in path:
            if directory not in node.children:
                return False
            node = node.children[directory]
        return True
    
    def isSubfolder(self, path: List[str]) -> bool:
        node = self.root
        for directory in path:
            if node.isLeaf:
                return True
            node = node.children[directory]
        return False

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = Trie()
        for path in folder:
            directories = path.split('/')
            trie.insert(directories)

        res = []
        for path in folder:
            directories = path.split('/')
            if not trie.isSubfolder(directories):
                res.append(path)
        return res






class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        result = []
        for f in sorted(folder):
            if not result or not f.startswith(result[-1] + '/'):
                result.append(f)
        return result
                
            
            


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()
        result = []
        splitted = list(map(lambda path: path.split('/')[1:], folder))
        numPath = len(folder)
        i = 0
        while i < numPath:
            result.append(folder[i])
            current = splitted[i]
            while i < numPath:
                remove = True
                for k in range(min(len(splitted[i]), len(current))):
                    if splitted[i][k] != current[k]:
                        remove = False
                        break
                if remove:
                    i += 1
                else:
                    break
        return result

class TrieNode:
    def __init__(self, name):
        self.children = {}
        self.isEnd = False
        self.name = name
        

class Trie:
    def __init__(self):
        self.root = TrieNode(\"\")
        
    def insert(self, word):
        it = self.root
        for w in word:
            if w not in it.children:
                it.children[w] = TrieNode(w)
                
            it = it.children[w]
        it.isEnd = True
    
    def normalize(self):
        self._normalize(self.root)
    
    def _normalize(self, node):
        if not node:
            return
        
        for char, childNode in node.children.items():
        
            hasSubFolders, child = self._normalize(childNode)
            if hasSubFolders and node.isEnd:
                node.children[child] = None

        return (node.isEnd, node.name)
        
    def getWords(self):
        lastWord = []
        result = []
        self._getWords(self.root, lastWord, result)
        return result
        
    def _getWords(self, node, lastWord, result):
        if not node:
            return
        
        if node.isEnd:
            result.append(\"/\".join(lastWord + [node.name]))
            return
        lastWord.append(node.name)
        for char, nodeChild in node.children.items():
            self._getWords(nodeChild, lastWord, result)
        lastWord.pop()
        


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = Trie()
        for folder in folder:
            trie.insert(folder.split(\"/\")[1:])
            
        trie.normalize()
        
        return trie.getWords()
        

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        
        trie = {}
        for f in folder:
            fo = f.split('/')
            curr = trie
            for letter in fo:
                if letter not in curr:
                    curr[letter] = {}
                curr = curr[letter]
            curr['#'] = f
        
        def dfs(curr):
            if '#' in curr:
                res.append(curr['#'])
                return
            for key in curr:
                dfs(curr[key])
        
        res = []
        dfs(trie)
        return res

class Node:
    def __init__(self, name):
        self.name = name
        self.subdir = {}
        self.terminal = False
        
    def link(self, name, node):
        self.subdir[name] = node

class Solution:
    def dfs(self, node, dirstr, found):
        #print(dirstr, found)
        rtn = []
        if node.terminal and not found:
            rtn = [dirstr]
        for x in node.subdir.keys():
            rtn = rtn + self.dfs(node.subdir[x], dirstr+'/'+x, (found|node.terminal))
        return rtn
    
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        root = Node('')
        for d in folder:
            seq = d.split('/')[1:]
            p = root
            for f in seq:
                if f not in p.subdir:
                    q = Node(f)
                    p.subdir[f] = q
                p = p.subdir[f]
            p.terminal = True
        return self.dfs(root, '', False)

class TrieNode:
    def __init__(self):
        self.children = collections.defaultdict(TrieNode)
        self.is_word = ''

class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        curr = self.root
        for ch in word:
            curr = curr.children[ch]
        curr.is_word = '/' + '/'.join(word)
    
    # def (self, node):
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = Trie()
        for path in folder:
            trie.insert(path.split('/')[1:])
        
        res = []
        
        def bfs(node):
            if node.is_word:
                res.append(node.is_word)
                return
            for child in list(node.children.values()):
                bfs(child)
        bfs(trie.root)
        return res
                
            


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        dit = set()
        arr = []
        folder.sort()
        for i in range(0, len(folder)):
            p = \"\"
            for a in range(0, len(folder[i])):
                p += folder[i][a]
                if a+1 < len(folder[i]):
                    if folder[i][a+1] == '/':
                        if p in dit:
                            break
                    elif folder[i][a+1] == None:
                        if p not in dit:
                            dit.add(p)
                            arr.append(p)
                else:
                    if p not in dit:
                        dit.add(p)
                        arr.append(p)
        return arr

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        def check(f):
            return all(map(lambda x: len(x) > 0, f.split('/')[1:]))
        def parent(f):
            parents = set()
            tmp = f.split('/')
            for i in range(1, len(tmp)-1):
                parents.add('/'.join(tmp[:i+1]))
            return parents
        folder.sort()
        seen = set()
        res = []
        for f in folder:
            if check(f):
                flag = False
                ps = parent(f)
                # print(f, ps)
                for p in ps:
                    if p in seen:
                        flag = True
                        break
                if not flag:
                    res.append(f)
                seen.add(f)
        return res

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        
        folder.sort(key = lambda x: len(x))
        res = []
        # while folder:
        #     e = folder.pop()
        #     for p in folder:
        #         if e.startswith(p) and e[len(p)] == '/':
        #                 e = ''   
        #                 break
        #     if e: res.append(e)
        # return res
    
        # trie = {}
        # for t in folder:
        #     m = trie
        #     parent = False
        #     for c in t.split('/'):
        #         m[c] = m.get(c, {})
        #         m = m[c]
        #         if '$' in m: 
        #             parent = True
        #             break
        #     if not parent:
        #         m[\"$\"] = '$'
        #         res.append(t)
        # return res
         
#             use stack and sort with lexinton
        files = sorted(folder)
        stack  = [files[0]]
        for i in range(1, len(files)):
            if not files[i].startswith(stack[-1] + '/'):  stack.append(files[i])
        return stack


class TrieTree:
    def __init__(self):
        self.children = {}
        self.isEnd = False
        self.endWord = None
    
class Solution:
    ##这个文件夹可能不是只有一个单词的！！
    def __init__(self):
        self.root = TrieTree()
        
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        for word in folder:
            wordList = word.split(\"/\")
            curr = self.root
            for letter in wordList:
                if letter not in curr.children:
                    curr.children[letter] = TrieTree()
                curr = curr.children[letter]
            curr.isEnd = True
            curr.endWord = word
            
        def dfs(root, path, result):
            if not root:
                return 
            
            if root.isEnd:
                result.append(root.endWord)
                return
            
            for i in root.children.keys():
                dfs(root.children[i], path + i, result)
            
        
        
        result = []
        dfs(self.root, \"\", result)
        return result
    
    

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort(key = lambda x: len(x))

        hashmap = set()

        for f in folder:
            seen = False
            for i in range(2, len(f)):
                if f[i] == \"/\" and f[:i] in hashmap:
                    seen = True
                    break
            
            if not seen: hashmap.add(f)

        return hashmap
        

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        root = {}
        for f in folder:
            f = f.split(\"/\")[1:]
            self.insert(root, f)
        return self.dfs([], root, [])
        
    def insert(self, root, f):
        for e in f:
            if e not in root:
                root[e] = {}
            root = root[e]
        root['#'] = '#'
    
    def dfs(self, tmp, root, fn):
        if '#' in root:
            fn.append('/' + '/'.join(tmp))
            return fn
        for k in root:
            #if k != '#':
            self.dfs(tmp+[k], root[k], fn)
        return fn
            
        

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = {}
        for f in folder:
            p = trie
            
            for c in f:
                if c not in p:
                    p[c] = {}
                p = p[c]
            if '/' not in p:
                p['/'] = {}
            p = p['/']
            p['$'] = f
        
        #print(trie)
        ans = []
        for f in folder:
            p = trie
            full = f+'/'
            for c in full:
                if '$' in p:
                    break
                p = p[c]
            else:
                ans.append(f)
        return ans

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEnd = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.isEnd = True  
    
    def find(self):
        def dfs(direc, node):
            if node.isEnd:
                answer.append('/' + '/'.join(direc))
                return
            for char in node.children:
                dfs(direc + [char], node.children[char])
        
        answer = []
        dfs([], self.root)
        return answer


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = Trie()
        for f in folder:
            f = f.split('/')[1:]
            #print(f)
            trie.insert(f)
        return trie.find()


class Node:
    def __init__(self, name):
        self.name = name
        self.next = dict()
        self.flag = False
        
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        head = dict()
        for f in folder:
            sub = f.split(\"/\")

            for i in range(1,len(sub)):
                if i == 1:
                    if sub[i] not in head:
                        head[sub[i]] = Node(sub[i])
                    node =  head[sub[i]]
                    if i == len(sub)-1:
                        node.flag = True
                elif i == len(sub) -1:
                    if sub[i] not in node.next:
                        node.next[sub[i]] = Node(sub[i])
                    node.next[sub[i]].flag = True
                else:
                    if sub[i] not in node.next:
                        node.next[sub[i]] = Node(sub[i])
                    node = node.next[sub[i]]
                    
            
        ret = list()
        # print(head)
        for k in head:
            # dfs
            stack = [(head[k], list())]
            while stack:
                node, chain = stack.pop()
                chain.append(node.name)
                if node.flag:
                    ret.append(\"/\"+\"/\".join(chain))
                else:
                    for k, next_node in node.next.items():
                        stack.append((next_node, list(chain)))
                        
            
            
            
            
            
        return ret
            
                    
                
                
                
                
        

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = {}
        for f in folder:
            p = trie
            full = f+'/'
            for c in full:
                if c not in p:
                    p[c] = {}
                p = p[c]
            p['$'] = full
        
        #print(trie)
        ans = []
        for f in folder:
            p = trie
            full = f+'/'
            for c in full:
                if '$' in p:
                    break
                p = p[c]
            else:
                ans.append(f)
        return ans

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        dic = set(folder)
        for x in folder:
            for i in range(len(x)):
                if i != 0 and x[i] == '/':
                    if x[:i] in dic:
                        dic.remove(x)
                        break 
        return list(dic)

class Node:
    def __init__(self, name):
        self.name = name
        self.next = dict()
        self.flag = False
        
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        head = dict()
        for f in folder:
            sub = f.split(\"/\")
            
            for i in range(1,len(sub)):
                # first node
                if i == 1:
                    node = head.setdefault(sub[i],  Node(sub[i]))

                    if i == len(sub)-1:
                        node.flag = True
                elif i == len(sub) -1:
                    if sub[i] not in node.next:
                        node.next[sub[i]] = Node(sub[i])
                    node.next[sub[i]].flag = True
                else:
                    if sub[i] not in node.next:
                        node.next[sub[i]] = Node(sub[i])
                    node = node.next[sub[i]]
                    
        ret = list()
        for k in head:
            # dfs
            stack = [(head[k], list())]
            while stack:
                node, chain = stack.pop()
                chain.append(node.name)
                if node.flag:
                    ret.append(\"/\"+\"/\".join(chain))
                else:
                    for k, next_node in node.next.items():
                        stack.append((next_node, list(chain)))

        return ret