Untitled

class TrieNode {
    TrieNode[] children;
    boolean isEnd;
    String str;

    TrieNode() {
        children = new TrieNode[26];
        isEnd = false; 
        str = ""; 
    }
}

class Solution {
    //o(L)
    public void insert(TrieNode root, String word) {
        TrieNode current = root;

        // Traverse each character in the word
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            current = current.children[index];
        }

        // Mark the end of the word and store the word
        current.isEnd = true;
        current.str = word;
    }

    public void dfs(TrieNode current, String ans[]) 
    {
    for (int i = 0; i < 26; i++) 
    {
        if (current.children[i] != null && current.children[i].isEnd) 
        {
            // Check if the current word should update the answer
            if (ans[0].length() < current.children[i].str.length()) 
            ans[0] = current.children[i].str;

            else if (ans[0].length() == current.children[i].str.length()) 
            {
                if(current.children[i].str.compareTo(ans[0]) < 0)
                ans[0] = current.children[i].str;
            }
            // Continue the DFS
            dfs(current.children[i], ans);
        }
    }
}

//Time->O(n*l)
public String longestWord(String[] words) {
    TrieNode root = new TrieNode();

    // Insert all words into the Trie
    for (String word : words) {. //O(n*L)
        insert(root, word);
    }

    // Use a String array to store the answer (mutable reference)
    String[] ans = {""};

    // Perform DFS to find the longest word
    dfs(root, ans);  //o(N*l)


    return ans[0];
}

}