Why not n^2 comparisons in the Alien Dictionary problem on leetcode?

Question

Here's the problem statement (as given on GeeksForGeeks website):

Given a sorted dictionary of an alien language having N words and k starting alphabets of standard dictionary, find the order of characters in the alien language.

Explanation: We're given a sorted dictionary having N words. Here a dictionary is an ordered list. A word is a sequence of allowed characters. There are 'K' allowed characters. These characters are first K alphabets of roman script. For example, K=5 implies that the allowed characters are {a, b, c, d, e}. But the ordering of the allowed characters is different in the alien language from standard roman script. For example, in the alien language the order of characters could be [b, d, e, a, c]. The words in the given dictionary are sorted lexicographically. Using the dictionary, we've to figure out the ordering of characters in the alien language.

Example test case: N = 5, K = 4, dict = ["baa","abcd","abca","cab","cad"]

Solution: {b, d, a, c}

Now the solution requires building a DAG. We iterate over the dictionary and compare every word to its next word to get information about the ordering of alphabets in the alien dictionary, i.e., pair-wise comparisons. In an optimal approach, (N-1) comparisons will be required to create the DAG (N being number of words in the dictionary). Every time we compare 2 word, we can infer something about the ordering of alphabets. This information is used to build the order of alphabets in the alien dictionary.

My first intuition was that every string in the dictionary can be compared to every string succeeding it thus totalling comparisons in order of N^2, i.e. [(n-1)+(n-2)+...+2+1] comparisons. But it turns out that N^2 comparisons aren't required. If we use only (N-1) comparisons as mentioned in previous paragraph, the information is sufficient to deduce the order of alphabets. How can I prove that the extra comparisons made in the N^2 approach will always be redundant giving no useful information?

Answer 1

Each pair of adjacent words $w_i,w_{i+1}$ in the dictionary list $[w_1,\ldots,w_N]$ generates at most one edge in the DAG. Why "at most"? (a) because that edge may be present already and (b) because $w_i$ could be a prefix of $w_{i+1}$. The suggested $N-1$ comparisons suffice because nothing new can be learned from studying $w_i,w_{i+\ell}$ for $\ell > 1$ that was not learned already by iterating through the $N-1$ adjacent pairs.

Let's prove that last claim. Roughly, this works as follows. Let $\Sigma$ be the alien alphabet. Suppose $m,n,o$ are minimal such that $m<n<o\leq N$ and comparing $w_m$ with $w_o$ adds the edge $(\alpha,\beta)$ to the DAG $(\Sigma,E)$ we obtained by comparing the $N-1$ pairs $(w_i,w_{i+1})$ for $1\leq i < N$ and then forming the transitive closure.

For easier access to the letters of the three relevant words, set $x_1\ldots x_{k_m} = w_m$, $y_1\ldots y_{k_n} = w_n$, and $z_1\ldots z_{k_o} = w_o$. We know there exists $j$ such that $\alpha = x_j \neq z_j = \beta$ and, for all $1\leq k<j$ we have $x_k = z_k$. (Otherwise we would not add $(\alpha,\beta)$.) We also know that $x_k = y_k = z_k$ for all $1\leq k<j$ and that $x_j\leq y_j\leq z_j$ according to $E$. One of those "$\leq$" is strict, i.e., already in $E$. Either way, since we formed the transitive closure, $(x_j,z_j)$ is already in $E$ (or this is not the minimal example of $m,n,o$).