In this explanation, we use specific symbols for notations such as strings, so please check the following as needed.

Symbols used in this explanation

• Hereafter, a sequence of countably infinite characters $c_0 c_1 c_2 \dots$ is also called a string. A string with finite length is called a finite string, and a string with infinite length is called an infinite string. The lexicographical order between strings (including infinite strings) is defined in the same way as the usual lexicographical order for finite strings (this also forms a total order. The proof is omitted).
• For a string $X = x_0 x_1 \dots$ and $0 \leq l \leq r \leq |X|$, the substring of $X$ $x_l x_{l+1} \dots x_{r-1}$ is denoted by $X[l, r)$.
• For a finite string $X$ and a string $Y$, their concatenation is denoted by $X * Y$, or simply $XY$.
• For a finite string $X$ and an integer $n \geq 0$, the string obtained by concatenating $n$ copies of $X$ is denoted by $X^n$. Also, the (infinite) string obtained by infinitely concatenating $X$ is denoted by $X^\infty$. For example, arc$^3=$ arcarcarc, abc$^\infty=$abcabcabca....
• For strings $X, Y$, the length of their longest common prefix is denoted by $\text{lcp}(X, Y)$.
• If $X$ and $Y$ satisfy $|X| \leq |Y|$ and $X = Y[0, |X|)$, then $X$ is said to be a prefix of $Y$. Furthermore, if $|X| < |Y|$, then $X$ is said to be a proper prefix of $Y$.
• If finite strings $X$ and $Y$ satisfy $|X| \leq |Y|$ and $X = Y[|Y|-|X|, |Y|)$, then $X$ is said to be a suffix of $Y$.
• For a sequence of strings $X = (X_1, \dots, X_n)$, the inversion number of $X$ is denoted by $\text{inv}(X) \coloneqq | \lbrace (i, j) \mid 1 \leq i < j \leq N, X_i > X_j \rbrace |$.

Lemmas on Strings

Before explaining the solution, we present two lemmas on strings. The proofs are provided at the end of this explanation.

Lemma 1

Let \(X, Y\) be non-empty finite strings.

1. \(X^\infty = Y^\infty \iff XY = YX\).
2. If \(X^\infty \neq Y^\infty\), then \(\text{lcp}(X^\infty, Y^\infty) = \text{lcp}(XY, YX)\).

Lemma 2

For non-empty finite strings \(X, Y\), it holds that \(XY < Y \iff X^\infty < Y\).

Restating the Problem

The operation of adding a common character to the end of each string and the operation of swapping adjacent strings can be interchanged without affecting the result. Therefore, if we consider performing all character addition operations first and then performing adjacent swaps, the problem is equivalent to the following problem:

• For a finite string \(X\), let \(f(X) = \text{inv}(S_1 X, S_2 X, \dots, S_N X)\). Minimize \(|X| + f(X)\).

Change in the Inversion Number

Let \(S\) be a sequence of strings \(S = (S_1, S_2, \dots, S_N)\). Also, for a string \(X\), let \(S(X) = (S_1 X, S_2 X, \dots, S_N X)\). To consider the change in the inversion number when adding a string \(X\), namely \(\text{inv}(S(X)) - \text{inv}(S)\), it suffices to consider only the pairs \((i, j)\) for which the order between \(S_i\) and \(S_j\) differs from the order between \(S_i X\) and \(S_j X\).

For a pair \((i, j)\) with \(1 \leq i, j \leq N, i\neq j\), consider what the order of \(S_i X\) and \(S_j X\) will be. Without loss of generality, we can assume \(|S_i| \leq |S_j|\).

If \(S_i\) is not a proper prefix of \(S_j\), for any finite string \(X\), it holds that \(S_i X < S_j X \iff S_i < S_j\). Thus, the order between \(S_i\) and \(S_j\) does not change before and after adding the string \(X\).

Consider when \(S_i\) is a proper prefix of \(S_j\), that is, when there is a non-empty finite string \(T\) such that \(S_j = S_i T\). Since \(S_i\) is a proper prefix of \(S_j\), we have \(S_i < S_j\). On the other hand, the order between \(S_i X\) and \(S_j X = S_i TX\) is the same as the order between \(X\) and \(TX\), which, according to Lemma 2, is the same as the order between \(X\) and \(T^\infty\). Therefore, the reversal of the order of \(S_i\) and \(S_j\) is equivalent to \(T^\infty < X\).

Considering the above, the change in inversion number is as follows: Let \(P \coloneqq \{(i, j) \mid 1 \leq i, j \leq N, S_i\text{ is a proper prefix of }S_j\}\). For \((i, j) \in P\), let \(T_{ij}\) be the string that satisfies \(S_j = S_i T_{ij}\). Then, the following holds:

\[ \begin{aligned} \text{inv}(S(X)) - \text{inv}(S) = |\lbrace(i, j) \in P \mid i < j, T_{ij}^\infty < X\rbrace| - |\lbrace(i, j) \in P \mid i > j, T_{ij}^\infty < X\rbrace| \end{aligned} \]

Solution

Since \(T_{ij}\) is a suffix of \(S_j\), there are at most \(L \coloneqq \sum_i |S_i|\) possible strings for \(T_{ij}\). For each suffix \(T\) of each \(S_j\), precompute the change in the inversion number when \(T^\infty < X\). This can be done in \(O(L)\) or \(O(L\log L)\) time by properly implementing it using trie or rolling hash. Beware that \(S_i\) may not be distinct.

Next, sort the infinite repetitions of each suffix in lexicographical order. When comparing the order of \(X^\infty\) and \(Y^\infty\), first compute \(l \coloneqq \text{lcp}(XY, YX)\). According to Lemma 1, if \(l = |X|+|Y|\), then \(X^\infty = Y^\infty\), and otherwise, comparing the \(l\)-th character (0-based) of \(X^\infty\) and \(Y^\infty\) allows for the comparison of \(X^\infty\) and \(Y^\infty\). The computation of \(l\) can take \(O(\log L)\) time using hash and binary search, for example. Additionally, using suffix array, LCP array, and sparse table for \(O(L \log L)\) time preprocessing allows for \(O(1)\) time computation per query (not required for this problem). Thus, the computational complexity of this sorting is \(O(L \log L)\) or \(O(L (\log L)^2)\).

Furthermore, for two adjacent suffixes \(A\) and \(B\) in the sorted sequence of suffixes, find the minimum value of \(|X|\) for \(X\) such that \(A^\infty < X < B^\infty\). This is equal to \(\text{lcp}(A^\infty, B^\infty) + 1\), which can be determined using the same procedure as for sorting. Then, by keeping the total contribution to the inversion number as a cumulative sum, it is possible to update the minimum value of \(|X| + f(X)\). Beware of the following:

• No string is greater than z\(^\infty\).
• Different strings can still have equal infinite repetitions.

---

Appendix: Proofs of Lemmas

Proof of Lemma 1

1. Let \(X = x_0x_1\dots x_{|X|-1}, Y=y_0y_1\dots y_{|Y|-1}, g = \text{gcd}(|X|, |Y|)\). More strongly, we show that the following three conditions are all equivalent, which yields the claim.
   1. \(X^\infty = Y^\infty\).
   2. \(X, Y\) both have \(g\) as a period.
   3. \(XY = YX\).

(ii. \(\Rightarrow\) i.) and (ii. \(\Rightarrow\) iii.) are obvious, so we show (i. \(\Rightarrow\) ii.) and (iii. \(\Rightarrow\) ii.).

(i. \(\Rightarrow\) ii.)

Assume integers \(i\) and \(j\) satisfy \(0 \leq i < |X|, 0 \leq j < |Y|, i \equiv j \bmod g\). By the Chinese remainder theorem, there exists an integer \(k \geq 0\) such that \(k \equiv i \bmod |X|, k \equiv j \bmod |Y|\). Comparing the \(k\)-th character of \(X^\infty = Y^\infty\) shows \(x_i = y_j\). Similarly, \(x_{i + g} = y_j\), so \(x_i = x_{i+g}\). Therefore, \(X\) has \(g\) as a period. The same applies to \(Y\).

(iii. \(\Rightarrow\) ii.)

Without loss of generality, we can assume \(|X| \leq |Y|\). Comparing each part of \(XY = YX\) shows \(Y[0, |X|) = Y [|Y| - |X|, |Y|) = X, Y[|X|, |Y|) = Y[0, |Y|-|X|)\). Therefore, \(Y^\infty\) has \(|X|\) as a period. Since \(|Y|\) is also clearly a period of \(Y^\infty\), eventually \(g = \gcd(|X|, |Y|)\) is also a period of \(Y^\infty\). Therefore, \(g\) is a period of \(Y\).



2. Assume \(X^\infty \neq Y^\infty\). From 1., \(XY \neq YX\). Without loss of generality, we can assume \(|X| \leq |Y|\). We divide into cases depending on whether \(Y\) is a prefix of \(X^\infty\).

   If \(Y\) is a prefix of \(X^\infty\)

   In this case, since \(|X| \leq |Y|\), \(X\) is a prefix of \(Y\). Thus, \(XY\) and \(YX\) are prefixes of \(X^\infty\) and \(Y^\infty\), respectively. From \(XY \neq YX\) and \(|XY| = |YX|\), it follows that \(\text{lcp}(X^\infty, Y^\infty) = \text{lcp}(XY, YX)\).

   If \(Y\) is not a prefix of \(X^\infty\)

   Take a string \(Y'\) and an integer \(n \geq 0\) such that \(Y = X^n Y'\) and \(X\) is not a prefix of \(Y'\). Since \(Y\) is not a prefix of \(X^\infty\), \(Y'\) is not a prefix of \(X\). Thus, \(\text{lcp}(X, Y') < \min\lbrace |X|, |Y'| \rbrace\), which leads to the following:

   \[ \begin{aligned} \text{lcp}(X^\infty, Y^\infty) & = \text{lcp}(X^nX^\infty, YY^\infty) \\ & = \text{lcp}(X^n*X^\infty, X^n*Y'Y^\infty) \\ & = n|X| + \text{lcp}(X^\infty, Y'Y^\infty) \\ & = n|X| + \text{lcp}(X, Y') \\ & = n |X| + \text{lcp}(XY', Y'X) \\ & = \text{lcp}(X^{n+1}Y', X^nY'X) \\ & = \text{lcp}(XY, YX). \end{aligned} \]

\(\blacksquare\)

Proof of Lemma 2

Take a string \(Y'\) and an integer \(n \geq 0\) such that \(Y = X^n Y'\) and \(X\) is not a prefix of \(Y'\). Then

\[ \begin{aligned} XY < Y & \iff X^{n+1} Y' < X^{n} Y' \\ & \iff X Y' < Y' \\ & \iff X < Y' \ (\because X \text{ is not a prefix of } Y') \\ & \iff X^\infty < Y\\ \end{aligned} \]

Therefore, the claim follows. \(\blacksquare\)