Q19 Alien Dictionary | Practice | GeeksforGeeks

//{ Driver Code Starts
/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
import java.math.*;

class GFG {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int t = Integer.parseInt(sc.next());
		while(t-- > 0)
		{
		    int n = Integer.parseInt(sc.next());
		    int k = Integer.parseInt(sc.next());
		    
		    String[] words = new String[n];
		    
		    for(int i=0;i<n;i++)
		    {
		        words[i] = sc.next();
		    }
		    
		    Solution ob = new Solution();
		  //  System.out.println(T.findOrder(words,k));
		    String order = ob.findOrder(words,n,k);
		    if(order.length() == 0){
		        System.out.println(0);
		        continue;
		    }
		    String temp[] = new String[n];
		    for(int i=0;i<n;i++)
		        temp[i] = words[i];
		    
		    Arrays.sort(temp, new Comparator<String>(){
		    
		      @Override
                public int compare(String a, String b) {
                    int index1 = 0;
                    int index2 = 0;
                    for(int i = 0; i < Math.min(a.length(), b.length()) 
                                        && index1 == index2; i++) {
                        index1 = order.indexOf(a.charAt(i));
                        index2 = order.indexOf(b.charAt(i));
                    }
                
                    if(index1 == index2 && a.length() != b.length()) 
                    {
                        if(a.length() < b.length())
                            return -1;
                        else
                            return 1;
                    }
                
                    if(index1 < index2)
                        return -1;
                    else
                        return 1;
                        
                }
		    });
		    
		    int flag = 1;
		    for(int i=0;i<n;i++)
		    {
		        if(!words[i].equals(temp[i]))
	            {
	                flag = 0;
	                break;
	            }
		    }
		    
		    System.out.println(flag);
		}
	}
	
}

// } Driver Code Ends


//User function Template for Java

class Solution
{
    public String findOrder(String [] dict, int n, int k)
    {//doesn't work on GFG , take a look once
        HashMap<Character , HashSet<Character>> graph = new HashMap<>();
        HashMap<Character,Integer> indegree = new HashMap<>();

        for(String word : dict){
            for(char ch : word.toCharArray())
            indegree.put(ch , 0);
        }
        //making graph between letters
        for(int i = 1 ; i < dict.length ; i++){
            String word1 = dict[i-1] , word2 = dict[i];
            
            int len = Math.min(word1.length() , word2.length());
            // System.out.println(word1 +" " + word2);
            for(int j = 0 ; j < len ; j++){
                char ch1 = word1.charAt(j) , ch2 = word2.charAt(j);
                
                // System.out.println(ch1 +" " + ch2);
                if(ch1 != ch2){
                    //making edge between ch1 and ch2
                    HashSet<Character> temp = graph.getOrDefault(ch1 , new HashSet<>());
                    temp.add(ch2);
                    graph.put(ch1 , temp);
                    
                    //increasing indegree of ch2 , and puttin indegree of ch1 = 0
                    indegree.put(ch2 , indegree.getOrDefault(ch2,0)+1);
                    
                    if(indegree.containsKey(ch1) == false)
                    indegree.put(ch1 , 0);
                    
                    break;
                }
            }
            
            //calling kahn's algo
        }
        
        return kahn(graph , indegree);
    }
    
    public String kahn(HashMap<Character , HashSet<Character>> graph,
    HashMap<Character,Integer> indegree){
        
        StringBuilder sb = new StringBuilder();
        
        LinkedList<Character> q = new LinkedList<>();
        
        //adding all nodes with indegree 0 
        for(char ch : indegree.keySet()){
            if(indegree.get(ch) == 0)
            q.addLast(ch);
        }
        //firing kahn
        
        while(q.size()>0){
            char ch = q.removeFirst();
            sb.append(ch+"");
            
            //reducing indegree of its neighours
            if(graph.containsKey(ch)){
                    for(char nbr : graph.get(ch)){
                    indegree.put(nbr , indegree.get(nbr)-1);
                    
                    //if indegree becomes 0 remove it and add to q
                    if(indegree.get(nbr) == 0){
                        indegree.remove(nbr);
                        q.addLast(nbr);
                    }
                    
                }
            }
        }
        
        return sb.toString();
    }
}