First, we need to sort the words in the order which corresponds to the permutation. Now we see that, after encoding, a word must be lexicographically smaller than all the words that come after it.

Word ~A~ is smaller than word ~B~ if one of the two conditions is met:

1. ~A~ is a prefix of ~B~
2. ~A~ and ~B~ differ in the ~i^\text{th}~ letter and ~A_i~ is lexicographically smaller than ~B_i~ (~A_i~ is the ~i^\text{th}~ letter of ~A~, ~B_i~ is the ~i^\text{th}~ letter of ~B~)

To ensure that ~A~ comes after ~B~ is not smaller than ~B~ because of the first condition, it is sufficient to observe all pairs and check if ~A~ is a prefix of ~B~.

The second condition is checked by constructing a directed graph consisting of ~26~ nodes, where each node represents one letter of the English alphabet. The graph contains a directed edge ~B_i \to A_i~ if and only if there exist words ~A~ and ~B~ such that ~A~ comes before ~B~ and they differ for the first time in the ~i^\text{th}~ letter. In other words, if there exists a directed edge ~B_i \to A_i~, then the letter that will be replaced with ~A_i~ must be lexicographically smaller than the letter which will be used to replace ~B_i~.

Obviously, the solution will not exist if there is a cycle in the graph. Given the fact that the number of nodes is quite small, a cycle can be detected in various ways. One of the simpler ways is using the Floyd–Warshall algorithm that performs in the time complexity ~\mathcal O(V^3)~, where ~V~ is the number of nodes.

If the graph doesn't have cycles, then the graph is DAG (directed acyclic graph), which means that its nodes can be topologically sorted. For each node ~X~, it holds that all nodes which are accessible from ~X~ in a topologically sorted array come before it.

From the aforementioned conditions, we can see that the letter that is represented by the first node in a topologically sorted array must be assigned the letter a, the second node the letter b, and so on.