/**
* Trie
*/
public class Solution {

    private TrieNode root;

    public Solution() {
        root = new TrieNode();
    }

    public void insert(String folder, int refValue) {
        TrieNode current = root;
        String[] parts = folder.split("/");
        for (String part : parts) {
            if (!part.isEmpty()) {
                current = current.getChildren().computeIfAbsent(part, k -> new TrieNode());
            }
        }
        current.setRef(refValue); // Store the folder reference
    }

    public boolean search(String folder) {
        return false;
    }

    public List<String> removeSubfolders(String[] folder) {
        for (int i = 0; i < folder.length; i++) {
            insert(folder[i], i);
        }
        List<String> ans = new ArrayList<>();
        dfs(root, ans, folder);
        return ans;
    }

    private void dfs(TrieNode node, List<String> ans, String[] folder) {
        if (node.getRef() != -1) {
            ans.add(folder[node.getRef()]);
            return;
        }
        for (Map.Entry<String, TrieNode> entry : node.getChildren().entrySet()) {
            TrieNode childNode = entry.getValue();
            dfs(childNode, ans, folder);
        }
    }

    class TrieNode {
        private final Map<String, TrieNode> children = new HashMap<>();
        private int ref = -1;

        public Map<String, TrieNode> getChildren() {
            return children;
        }

        public void setRef(int ref) {
            this.ref = ref;
        }

        public int getRef() {
            return ref;
        }
    }
}


/**
* Sort
*/
class Solution {
    public List<String> removeSubfolders(String[] folder) {
        List<String> ans = new ArrayList<>();
        Arrays.sort(folder);
        ans.add(folder[0]);
        for (int i = 1; i < folder.length; i++) {
            String curr = folder[i];
            int currLen = curr.length();
            String prev = ans.get(ans.size() - 1);
            int prevLen = prev.length();
            if (currLen > prevLen && curr.startsWith(prev) && curr.charAt(prevLen) == '/') {
                // current folder is a subfolder of the last added folder
                continue;
            }
            ans.add(curr);
        }
        return ans;
    }
}