class Solution {

    class TrieNode {
        String name;
        String hashValue;
        Map<String, TrieNode> childNodes;

        TrieNode() {
            childNodes = new HashMap<>();
        };

        TrieNode(String name) {
            childNodes = new HashMap<>();
            this.name = name;
        }

        public void insert(List<String> path) {
            TrieNode cur = this;
            for(String node : path){
                if(!cur.childNodes.containsKey(node)){
                    cur.childNodes.put(node, new TrieNode(node));
                }
                cur = cur.childNodes.get(node);
            }
        }
    }

    public void serialize(TrieNode root, Map<String,Integer> pathsMap) {
        if(root.childNodes.isEmpty()) {
            return;
        }
        StringBuilder sb = new StringBuilder();

        List<String> childNodes = new ArrayList<>(root.childNodes.keySet());
        Collections.sort(childNodes);

        for(String childName : childNodes) {
            TrieNode childTrie = root.childNodes.get(childName);
            sb.append("(");
            serialize(childTrie, pathsMap);
            sb.append(childName);
            if(!childTrie.childNodes.isEmpty()) sb.append(",").append(childTrie.hashValue);
        }
        root.hashValue = sb.append(")").toString();
        pathsMap.put(root.hashValue, pathsMap.getOrDefault(root.hashValue, 0) + 1);
    }

    public void deleteDuplicateNode(TrieNode root, Map<String,Integer> pathsMap) {
        if(root.childNodes.isEmpty())
            return;

        List<String> childNodes = new ArrayList<>(root.childNodes.keySet());
        Collections.sort(childNodes);

        for(String childName : childNodes){
            TrieNode childNode = root.childNodes.get(childName);
            deleteDuplicateNode(childNode, pathsMap);
            if(pathsMap.containsKey(childNode.hashValue) && pathsMap.get(childNode.hashValue) > 1) {
                root.childNodes.remove(childName);
            }
        }
    }

    public void generateResult(TrieNode root, List<String> list, List<List<String>> result) {
        if(!list.isEmpty()) {
            result.add(new ArrayList<>(list));
        }

        for(String childName : root.childNodes.keySet()) {
            list.add(childName);
            TrieNode childNode = root.childNodes.get(childName);
            generateResult(childNode, list, result);
            list.remove(list.size() - 1);
        }
    }

    public List<List<String>> deleteDuplicateFolder(List<List<String>> paths) {

        // Xay dung cay Trie
        TrieNode root = new TrieNode();
        for(List<String> path : paths){
            root.insert(path);
        }

        // Tinh gia tri bam cua tung nut trong cay va luu vao pathsMap
        Map<String,Integer> pathsMap = new HashMap<>();
        serialize(root, pathsMap);

        // Xoa cac cay thu muc con trung lap
        deleteDuplicateNode(root, pathsMap);

        // Tao mang ket qua
        List<List<String>> result = new ArrayList<>();
        generateResult(root, new ArrayList<>(), result);

        return result;
    }
}