String Distance
Contest: Educational Codeforces Round 110 (Rated for Div. 2)
Difficulty rating: 3000
Tags: binary search, brute force, data structures, hashing, implementation, strings

Suppose you are given two strings $$$a$$$ and $$$b$$$. You can apply the following operation any number of times: choose any contiguous substring of $$$a$$$ or $$$b$$$, and sort the characters in it in non-descending order. Let $$$f(a, b)$$$ the minimum number of operations you have to apply in order to make them equal (or $$$f(a, b) = 1337$$$ if it is impossible to make $$$a$$$ and $$$b$$$ equal using these operations).

For example:

- $$$f(\text{ab}, \text{ab}) = 0$$$;
- $$$f(\text{ba}, \text{ab}) = 1$$$ (in one operation, we can sort the whole first string);
- $$$f(\text{ebcda}, \text{ecdba}) = 1$$$ (in one operation, we can sort the substring of the second string starting from the $$$2$$$-nd character and ending with the $$$4$$$-th character);
- $$$f(\text{a}, \text{b}) = 1337$$$.

You are given $$$n$$$ strings $$$s_1, s_2, \dots, s_k$$$ having equal length. Calculate $$$\sum \limits_{i = 1}^{n} \sum\limits_{j = i + 1}^{n} f(s_i, s_j)$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of strings.

Then $$$n$$$ lines follow, each line contains one of the strings $$$s_i$$$, consisting of lowercase Latin letters. $$$|s_1| = |s_2| = \ldots = |s_n|$$$, and $$$n \cdot |s_1| \le 2 \cdot 10^5$$$. All these strings are pairwise distinct.

Output format:
Print one integer: $$$\sum \limits_{i = 1}^{n} \sum\limits_{j = i + 1}^{n} f(s_i, s_j)$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 1024.0 MB

Example input:
4
zzz
bac
abc
acb

Example output:
4015

Example input:
2
a
b

Example output:
1337

Editorial:
Disclaimer: the model solution is very complicated compared to most participants' solutions. Feel free to discuss your approaches in the comments!
First of all, it's easy to determine when two strings cannot be made equal using these operations: it's when their multisets of characters differ. So, we divide the strings into different equivalence classes, and for any pair of strings from different classes, the answer is $$$1337$$$. For any pair of strings from the same class, the answer is either $$$1$$$ or $$$2$$$, since $$$2$$$ operations are always enough to make the strings from the same equivalence class equal (we just sort both of them). Okay, now, for each class, we have to calculate the number of pairs of strings with the distance equal to $$$1$$$.
Okay, suppose you have two strings $$$s_1$$$ and $$$s_2$$$, and you want to make them equal using one operation. Suppose that $$$s_1 < s_2$$$ lexicographically. Since applying an operation can't result in getting a lexicographically larger string, we should apply the operation on the string $$$s_2$$$, not $$$s_1$$$.
Suppose we choose a substring $$$[l, r]$$$ of the string $$$s_2$$$ and sort it. All characters to the left of position $$$l$$$ and to the right of position $$$r$$$ are untouched, and all characters in $$$[l, r]$$$ are ordered in non-descending order; so, in order to transform $$$s_2$$$ into $$$s_1$$$, we should choose a subsegment $$$[l, r]$$$ such that all characters outside this segment are the same in both strings, and the substring $$$[l, r]$$$ of $$$s_1$$$ is sorted. So, the best way to choose a subsegment $$$[l, r]$$$ is to compute the longest common prefix of $$$s_1$$$ and $$$s_2$$$, the longest common suffix of $$$s_1$$$ and $$$s_2$$$, and try sorting everything in the middle in $$$s_2$$$.
This gives us a solution in $$$O(n^2)$$$: for a pair of strings, we can check that one of them can be transformed into the other in $$$O(1)$$$. To do so, we need to build some data structure allowing to query longest common prefixes/suffixes in $$$O(1)$$$ (a trie with $$$O(1)$$$ LCA or precalculating LCP and building a sparse table of them can do the trick); furthermore, we want to be able to check if some subsegment of some string is sorted in $$$O(1)$$$ (but precalculating them is quite easy). So, we have a solution that works if the strings are long (in the model solution, this approach is used on classes having not more than $$$12000$$$ strings).
The second approach can be used on classes having many strings. If the number of strings is big, it means that they are short, so we can do the following thing: for each string, iterate on the subsegment we will sort and check if the resulting string exists. The model solution uses some very complicated data structures to implement this, but I believe that it's quite easy to get this approach working using string hashes.
The only dangerous thing in the second solution you have to consider is that choosing different substrings to sort may result in getting the same resulting string. One good way to deal with this is to ignore some substrings if sorting them doesn't change the leftmost or the rightmost character in the substring; for example, if we sort the substring acb in the string zacb, the character in the beginning of this substring is unchanged, so we can get the same result by sorting cb. So, we consider sorting the substring only if it changes both the first and the last characters of the substring.
Okay, so we have two approaches: one works well with a small number of long strings, and the other works well with a big number of short strings. We can choose which of them to run depending on the size of the equivalence class we are considering, and this idea gives us a working solution.