New update is available. Click here to update.

Last Updated: 20 Feb, 2021

Hard

```
Let us assume that we have a list of words found in the dictionary in the same order as given: [βbaaβ, βabcdβ, βabcaβ, βcabβ, βcadβ]
Now, ninja needs to find the order of the characters used in these strings.
The order would be: βbβ, βdβ, βaβ, βcβ, because βbaaβ comes before βabcdβ, hence βbβ will come before βaβ in the order, similarly because, βabcdβ comes before βabcaβ, βdβ will come before βaβ. And so on.
```

```
A certain list of words might have more than one correct order of characters. In such cases, you need to find the smallest in normal lexicographical order. In the case of INVALID ORDER, simply return an empty string.
```

```
words = [βabaβ, βbbaβ, βaaaβ].
In this case, no valid order is possible because, from the first two words, we can deduce βaβ should appear before βbβ, but from the last two words, we can deduce βbβ should appear before βaβ which is not possible.
```

```
words = [βcaβ, βcbβ].
In this case, we only know that βbβ will come after βaβ in the order of characters, but we don't have any knowledge of βcβ. So, the valid correct orders can be = βabcβ, βcabβ, βacbβ. Out of these, βabcβ is lexicographically smallest, hence it will be printed.
```

```
The first line contains a single integer βTβ representing the number of test cases.
The first line of each test case will contain an integer βNβ, which denotes the number of words in the dictionary.
The second line of each test case will contain βNβ space-separated strings which denote the words of the dictionary.
```

```
For each test case, print the order of characters.
Output for every test case will be printed in a separate line.
```

```
1 <= T <= 10
1 <= N <= 300
0 <= size <= 100
Time limit: 1 sec
```

Approaches

The idea behind this approach is to create a graph of the words of the dictionary and then apply the topological ordering of the graph.

**A topological ordering** of a directed graph is a linear ordering of its vertices such that for every directed edge **u v** from vertex **u** to vertex **v**, **u** comes before **v** in the ordering.

The approach is to take two words from the array of words and then compare characters of both words and find the first character that is not the same in the words.

Then, create an edge in the graph from the first different character of the first word to the second word.

Finally, apply topological sorting in the above-created graph.

Let us understand this better by dividing the complete solution into two parts:

- Graph Creation:
- We will use unordered_map to store the graph. The graph will be created by using below steps:
- Weβll start with two words, letβs say
**a**and**b.**Now we find the smaller word from the two, so that we could just traverse to that position.- Letβs say a has 3 characters and b has 5 characters. Now in order to find the first mismatched character we traverse from start to the length of the smaller word and check each character, until we find the first mismatched character.
- Now, we simply create an edge between the first mismatched character of the first word to the second word.
- Continue this process until all the edges are created.
- Now, we will have a graph created with 1st mismatched character from each word to the other.

- Weβll start with two words, letβs say

- We will use unordered_map to store the graph. The graph will be created by using below steps:
- Now, apply the topological sort in the created graph in order to find the required order.
- Topological Sorting:
- The topological sorting algorithm is used in directed graphs(like the one we created), in which we need to find an order of edges such that every edge leads from the vertex of a smaller value assigned to the larger value. To read more about
**topological sorting**you can refer: https://cp-algorithms.com/graph/topological-sort.html - Basically, we start from a vertex letβs say
**v**and run along all edges that are outgoing from the same. This will not move along the edges for which the destination vertex has already been visited.- Continue the same process from the rest of the edges and then start from them,
- By the end of this method, all vertices would be reached from the starting vertex
**v**either directly or indirectly. - Finally, we will use a queue to store the topological order of all vertices.

- The topological sorting algorithm is used in directed graphs(like the one we created), in which we need to find an order of edges such that every edge leads from the vertex of a smaller value assigned to the larger value. To read more about

**Algorithm + Pseudo Code:**

- Define a map letβs say
**βdegreeβ.** - Define another map letβs say
**βgraphβ**. - Now initialize i from i = 0 to i < size of words, while updating i by one in each traversal and, do β
- Initialize another var j from j = 0 to j < size of words, while updating j by one in each traversal and, do β
- degree[words[i, j]] := 0

- Initialize another var j from j = 0 to j < size of words, while updating j by one in each traversal and, do β
- Next initialize i from i = 0 to i < (size of words - 1), while updating i by one in each traversal and, do β
- Initialise a var
**βminiβ**:= minimum of size of words[i] and size of words[i + 1]. In order to find the smaller word, we could traverse only to that value. - Initialise j from j = 0 to j < mini, while updating j by one in each traversal and, do β
- Store in a var
**x**:= words[i, j] - Store in a var
**y**:= words[i + 1, j] - If x is not equal to y, then β (First different character found)
- insert y at the end of βgraph[x]β
- (increase degree[y] by 1)
- Come out from the loop

- Store in a var

- Initialise a var
**βresultβ**:= Initialise a blank string to store the final order- Initialise a queue
**βqueβ** - For each key-value pair letβs say
**βiterβ**in βdegreeβ, do β- if value of βiterβ is same as 0, then β
- insert key of it into βqueβ

- if value of βiterβ is same as 0, then β
- Now, while (not βqueβ is empty), do β
- x := first element of βqueβ
- delete element from βqueβ
- result := result + x
- for every element letβs say
**βelemβ**in βgraphβ do β- decrease degree[elem] by 1
- Now, if degree[elem] is same as 0, then β
- insert βelemβ into βqueβ

- (increase βelemβ by 1)

- return (if size of βresultβ is same as the size of βdegreeβ, then result, otherwise return a blank string)

Keep in mind the following cases:

- The longer string with the same prefix comes first, will make it an invalid case.
- In case of more than one correct order, simply return the lexicographical smallest order.