Day 100: Find the longest string

/*

Find the longest string


Given an array of strings arr[]. You have to find the longest string which is lexicographically smallest and also all of its prefix strings are already present in the array.

 

Example 1:

Input: ab a abc abd
Output: abc
Explanation: We can see that length of the longest 
string is 3. And there are two string "abc" and "abd"
of length 3. But for string "abc" , all of its prefix
"a" "ab" "abc" are present in the array. So the
output is "abc".
Example 2:

Input: ab a aa abd abc abda abdd abde abdab
Output: abdab
Explanation: We can see that each string is fulfilling
the condition. For each string, all of its prefix 
are present in the array.And "abdab" is the longest
string among them. So the ouput is "abdab".
 

Your Task:  
You don't need to read input or print anything. Your task is to complete the function longestString() which takes the array arr[] as input parameter and returns the longest string which is also lexicographically smallest.And if there is no such string return empty string.
 

Expected Time Complexity: O(NlogN)
Expected Space Complexity: O(N)

 

Constraints:
1 <= length of arr[] <= 103
1 <= arr[i].length <=30
*/

//{ Driver Code Starts
import java.io.*;
import java.util.*;


class StringArray
{
    public static String[] input(BufferedReader br, int n) throws IOException
    {
        String[] s = br.readLine().trim().split(" ");
        return s;
    }

    public static void print(String[] a)
    {
        for(String e : a)
            System.out.print(e + " ");
        System.out.println();
    }

    public static void print(ArrayList<String> a)
    {
        for(String e : a)
            System.out.print(e + " ");
        System.out.println();
    }
}

class GFG {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t;
        t = Integer.parseInt(br.readLine());
        while(t-- > 0){
            
            int n;
            n = Integer.parseInt(br.readLine());
            
            
            String[] arr = StringArray.input(br, n);
            
            Solution obj = new Solution();
            String res = obj.longestString(n, arr);
            
            System.out.println(res);
            
        }
    }
}

// } Driver Code Ends


class Solution {
    public static class TrieNode{
        TrieNode[] node;
        boolean isWord=false;
        TrieNode() {
            node = new TrieNode[26];
        }
    }
    
    public static void addWord(TrieNode root,String s) {
        int idx;
        for(int i=0;i<s.length();i++) {
            idx = s.charAt(i)-'a';
            if(root.node[idx]==null) root.node[idx] = new TrieNode();
            root = root.node[idx];
        }
        root.isWord=true;
    }
    
    public static boolean isValid(TrieNode root,String s) {
        int idx;
        for(int i=0;i<s.length();i++) {
            idx = s.charAt(i)-'a';
            // if(root.node[idx]==null) return false;
            root = root.node[idx];
            if(!root.isWord) return false;
        }
        return true;
    }
    
    public static String longestString(int n, String[] arr) {
        // code here
        TrieNode root = new TrieNode();
        for(String s : arr) {
            addWord(root,s);
        }
        String ans ="";
        for(String s : arr) {
            if(isValid(root,s)) {
                if(ans.length()<s.length()) {
                    ans=s;
                } else if(ans.length()==s.length()) {
                    if(ans.compareTo(s)>0) ans=s;
                }
            }
        }
        return ans;
    }
}