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.