Given a sorted dictionary of words, find order of precedence of letters This question is found at: https://www.geeksforgeeks.org/given-sorted-dictionary-find-precedence-characters/

Given a sorted dictionary (array of words) of an alien language, find order of characters in the language.

Examples:

Input:  words[] = {"baa", "abcd", "abca", "cab", "cad"}
Output: Order of characters is 'b', 'd', 'a', 'c'
Note that words are sorted and in the given language "baa" 
comes before "abcd", therefore 'b' is before 'a' in output.
Similarly we can find other orders.

Input:  words[] = {"caa", "aaa", "aab"}
Output: Order of characters is 'c', 'a', 'b'


Notice that the solution calls for comparison of adjacent word-pairs only, when discovering new edges. It is unnecessary to add edges from comparing non-adjacent words. This seems straightforward and intuitive to me, but how do we prove it?

An edge-discovery is done by comparing two strings, iterating through their characters, and finding the first pair of characters which differ. The former string's character precedes the latter string's character. In the case of the former string being a substring of the latter, then the edge discovery fails to return a pair. (It's impossible for the latter string to be a substring of the former)

Given a directed acyclic graph built from pairwise edge-discoveries of adjacent pairs &lt;word[1], word[2]&gt;, &lt;word[2], word[3]&gt;, ..., &lt;word[n-1], word[n]&gt;. Prove that comparing any two words which are not adjacent will not yield any new information, i.e. the edge-ordering discovered by the new comparison will already have been present, or implied by transitivity of edge-orderings in the existing graph.

Edit to add: I have a prefix-tree-based proof, but I'm no good at writing proofs and would welcome better-written proofs.
Let's denote the words by $w[1],\ldots,w[n]$. Suppose that $i &lt; j$ and that $w[i],w[j]$ first differ on the $t$th coordinate. In symbols, $w[i]_{&lt;t} = w[j]_{&lt;t}$ but $w[i]_t &lt; w[j]_t$ (I hope the notation is obvious).

I first claim that $w[k]_{&lt;t} = w[k+1]_{&lt;t}$ for all $k \in \{i,\ldots,j-1\}$. Indeed, suppose that $w[k]_{&lt;t} &lt; w[k+1]_{&lt;t}$ for some $k \in \{i,\ldots,j-1\}$. Then $w[i]_{&lt;t} \leq w[k]_{&lt;t} &lt; w[k+1]_{&lt;t} \leq w[j]_{&lt;t}$, contradicting the assumption $w[i]_{&lt;t} = w[j]_{&lt;t}$.

Call an index $k \in \{i,\ldots,j-1\}$ special if $w[k]_t &lt; w[k+1]_t$. Let the special indices be $k_1,\ldots,k_m$. Then
$$
w[i]_t = w[k_1]_t &lt; w[k_1+1]_t = w[k_2]_t &lt; w[k_2+1]_t \cdots w[k_m]_t &lt; w[k_m+1]_t = w[j]_t.
$$
This shows that $w[i]_t &lt; w[j]_t$ follows from $w[k_1]_t &lt; w[k_1+1]_t,\ldots,w[k_m]_t &lt; w[k_m+1]_t$ by transitivity. (Here we are using the fact, proved earlier, that $w[k_r]_{&lt;t} = w[k_r+1]_{&lt;t}$ for $r \in \{1,\ldots,t\}$.)