Alien Dictionary: 

There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you. 

You are given a list of strings words from the alien language's dictionary, where the strings in words are  

sorted lexicographically 

 by the rules of this new language. 

Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there is no solution, return "". If there are multiple solutions, return any of them. 

  

Example 1: 

Input: words = ["wrt","wrf","er","ett","rftt"] 

Output: "wertf" 

Example 2: 

Input: words = ["z","x"] 

Output: "zx" 

Example 3: 

Input: words = ["z","x","z"] 

Output: "" 

Explanation: The order is invalid, so return "". 

  

Constraints: 

• 1 <= words.length <= 100 

• 1 <= words[i].length <= 100 

• words[i] consists of only lowercase English letters. 

 

class Solution { 

    public String alienOrder(String[] words) { 

        StringBuilder sb = new StringBuilder(); 

        if (words == null || words.length == 0) { return sb.toString(); } 

 

        Character after = null; 

        for (int i = 0; i < words.length; i++) { 

            for (int j = 0; j < words[i].length(); j++) { 

                if ( i > 0 ) { 

                    int match = 0; 

                    while (match < words[i-1].length() &&  

                            match < words[i].length() &&  

                            words[i-1].charAt(match) == words[i].charAt(match)) 

                    { 

                        after = words[i-1].charAt(match); 

                        match++; 

                    } 

                    if (match != 0 && match < words[i-1].length()) { 

                        after = words[i-1].charAt(match); 

                    } 

                    if (match == 0){ 

                        after = words[i-1].charAt(match); 

                    } 

                    int afterIndex = after != null ? sb.indexOf(String.valueOf(after)) : -1; 

                    int index = sb.indexOf(String.valueOf(words[i].charAt(match))); 

                    if (index != -1 && afterIndex != -1 && index < afterIndex) { 

                        return ""; 

                    } 

                } 

 

                int afterIndex = after != null ? sb.indexOf(String.valueOf(after)) : -1; 

                int index = sb.indexOf(String.valueOf(words[i].charAt(j))); 

                if (index == -1) { 

                    System.out.println(sb.toString()); 

                    sb.insert(afterIndex+1, String.valueOf(words[i].charAt(j))); 

                } 

 

                after = words[i].charAt(j); 

            } 

        } 

 

        return sb.toString(); 

    } 

}