class Solution {
    public List<String> removeSubfolders(String[] folder) {
        //sort on the basis of length
        // by this way all the subfolders will always appear after their parent folders
        //example: ["/ah/al/am","/ah/al"] after sorting ["/ah/al","/ah/al/am"]
        Arrays.sort(folder,(a,b)->a.length()-b.length());
        List<String> list = new ArrayList<>();
        Trie t = new Trie();
        for(String s : folder){
            if(t.insert(s,t)){
                list.add(s);
            }
        }
        return list;
    }
}

class Trie{
    boolean end = false;
    Map<String,Trie> map;
    public Trie(){
        map = new HashMap<>();
    }

    public boolean insert(String string, Trie root){
        Trie temp = root;
        String str[] = string.split("/");
        int i =0;
        for(String s : str){
            if(s.equals("")) continue;

            if(!temp.map.containsKey(s)){
                temp.map.put(s,new Trie());
            }
            if(temp.end) return false;
            temp  = temp.map.get(s);
        }
        temp.end = true;
        return true;
    }
}

class Solution {
    public List<String> removeSubfolders(String[] folder) {

        Arrays.sort(folder,(a,b)->a.length()-b.length());
        List<String> list = new ArrayList<>();
        Trie t = new Trie();

        // add all the folders in trie
        for(String s : folder){
            t.insert(s,t);

        }
        // check which folders are subfolders and don't add them in the final result list
        for(String s : folder){
            if(t.canAdd(s,t)){
                list.add(s);
            }
        }
        return list;
    }
}

class Trie{
    boolean end = false;
    Map<String,Trie> map;
    public Trie(){
        map = new HashMap<>();
    }

    //insert
    public void insert(String string, Trie root){
        Trie temp = root;
        String str[] = string.split("/");
        int i =0;
        for(String s : str){
            if(s.equals("")) continue;

            if(!temp.map.containsKey(s)){
                temp.map.put(s,new Trie());
            }
            temp  = temp.map.get(s);
        }
        temp.end = true;
    }

    public boolean canAdd(String string, Trie root){
        Trie temp = root;
        String str[] = string.split("/");
        int i =0;//keep counter
        for(String s : str){
            if(s.equals("")) continue;
            if(!temp.map.containsKey(s)){
                temp.map.put(s,new Trie());
            }
            //if i<str.length and temp.end = true it means that this must be a subfolder because it is 
            //present inside of a praent folder
            //example : parent could be /abc
            //subfolder could be (in this case) : /abc/pqr
            //so we will get temp.end= true before we are finished with all the the string in str or subfolders
            if(temp.end) return false;
            temp  = temp.map.get(s);
            i++;
        }
        return true;
    }
}