題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🟣 ABC434F Concat (2nd)

Problem Statement

題目簡述

給定 $N$ 個由小寫英文字母組成的字串 $S_1, S_2, \dots, S_N$ 。
對於所有長度為 $N$ 的排列 $P = (P_1, P_2, \dots, P_N)$ ，我們依序將 $S_{P_1}, S_{P_2}, \dots, S_{P_N}$ 拼接在一起，形成一個新字串。
共有 $N!$ 種可能的排列，這會生成 $N!$ 個字串。將這些字串按字典序從小到大排序，形成序列 $A_1, A_2, \dots, A_{N!}$ 。
請輸出字典序第二小的字串 $A_2$ 。

每組輸入包含 $T$ 個測試筆數。

Constraints

約束條件

$1 \le T \le 1.5 \times 10^5$
$2 \le N \le 3 \times 10^5$
$S_i$ 是由小寫英文字母組成的字串，且 $1 \le |S_i| \le 10^6 - 1$ 。
在同一組測試中，所有測試筆數的 $N$ 之和不超過 $3 \times 10^5$ 。
在同一組測試中，所有測試筆數的 $|S_i|$ 之和不超過 $10^6$ 。

思路：第二小的貪心交換

先把「如何排出第一小」當成已知前提：若兩個字串 $X, Y$ 滿足 $X + Y < Y + X$ ，就讓 $X$ 排在 $Y$ 前面。依照這個規則排序後，得到的序列記為 $A$ ，直接拼接就是字典序最小的字串。

真正需要處理的是：在這個最小排列之外，哪一個不同排列會產生第二小的拼接結果？

等價交換：最小字串可能同時也是第二小

如果排序後存在相鄰兩個字串滿足

A_i + A_{i+1} = A_{i+1} + A_i

那麼交換它們不會改變拼接結果，卻會得到另一個不同排列。因此排列序列中的第一名與第二名對應到同一個字串，答案就是最小字串本身。

Example

ab 與 abab 就是典型例子：

1 2	ab + abab = ababab abab + ab = ababab

兩個排列不同，但拼接結果完全相同。

接下來只需要討論沒有等價相鄰對的情況。此時每一組相鄰元素都嚴格滿足

A_i + A_{i+1} < A_{i+1} + A_i

候選只會來自一次相鄰交換

若某個排列相對於最小排列有至少兩個逆序對，就可以先修正其中一個逆序對，得到一個仍然不同於最小排列、但字典序更小的排列。換句話說，這種排列前面至少已經有「最小排列」與「修正一個逆序後的排列」，所以不可能是第二小。

因此第二小只可能來自恰好一次相鄰交換。令 $T_i$ 表示交換排序後第 $i$ 個與第 $i+1$ 個字串後得到的拼接結果。

在所有 $T_i$ 裡，多數位置其實可以直接淘汰：若交換位置太前面，它會比「交換最後兩個」更早破壞最小前綴，而且破壞處一定比較大。

證明：為何只剩最後兩種候選？

先比較 $T_i$ 與 $T_{N-1}$ ，其中 $i \le N-3$ 。

兩者共享前綴 $A_1 A_2 \dots A_{i-1}$ 。接著：

$T_i$ 會接上 $A_{i+1} A_i$ ，因為它在這裡交換。
$T_{N-1}$ 仍接上 $A_i A_{i+1}$ ，因為它只交換最後兩個。

由於目前沒有等價相鄰對，必有

A_i A_{i+1} < A_{i+1} A_i

且這兩段長度相同，都是 $|A_i| + |A_{i+1}|$ 。所以在第一次不同的字元處， $T_{N-1}$ 的字元一定更小；後面接什麼都無法扭轉這個結果。

因此所有 $i \le N-3$ 的交換都會被 $T_{N-1}$ 淘汰。

唯一不能直接淘汰的是 $T_{N-2}$ 。它與 $T_{N-1}$ 的分歧位置不同，不是在同一組對齊區塊上比較，所以必須保留下來實際比較。

所以當 $N > 2$ 且不存在等價相鄰對時，答案只需要在兩個候選中取較小者：

候選 1：交換最後兩個
$A_1 A_2 \dots A_{N-2} A_N A_{N-1}$
候選 2：交換倒數第三與倒數第二個
$A_1 A_2 \dots A_{N-3} A_{N-1} A_{N-2} A_N$

若 $N = 2$ ，兩個排列就是第一小與第二小，因此直接交換兩個字串輸出即可。

Example

假設排序後的序列是 ["a", "aab", "b"]。

交換最後兩個："a" + "b" + "aab" = "abaab"
交換前兩個："aab" + "a" + "b" = "aabab"

雖然交換前兩個比較早破壞前綴，但整體字典序反而更小，因此倒數兩種候選都要實際比較。

排序瓶頸

這題的主要瓶頸不在後面的候選比較，而在排序。比較兩個字串時會用到 $X + Y$ 與 $Y + X$ ，單次比較可能掃過 $\mathcal{O}(|X| + |Y|)$ 個字元；若排序過程反覆比較同一批長字串，就可能超時。

Python 的 sort() 使用 Timsort，可以搭配這個比較方式通過，但注意使用 PyPy 時，若使用 cmp_to_key 仍然會 TLE，必須使用繼承自 str 的自定義類別並覆寫 __lt__ 方法；C++ 若使用 std::sort，則需要注意針對性測資造成的退化風險，但可以透過 random_shuffle 來避免。關於詳細的複雜度分析請參考：

參考資料

複雜度分析

時間複雜度： $\mathcal{O}(\sum |S_i| \log^2 N)$ $O (\sum ∣ S_{i} ∣ lo g^{2} N)$
- 排序是主導項；後續檢查等價相鄰對、構造並比較兩個候選都是線性時間。
空間複雜度： $\mathcal{O}(\sum |S_i| + N)$ $O (\sum ∣ S_{i} ∣ + N)$
- 主要用於儲存字串序列，以及拼接候選時產生的暫存字串。

Code

from itertools import pairwise
from functools import cmp_to_key


class C(str):
    def __lt__(self, other):
        return self + other < other + self


def solve():
    N = int(input())
    words = [input() for _ in range(N)]

    def cmp(x, y):
        xy = x + y
        yx = y + x
        return (xy > yx) - (xy < yx)

    # words.sort(key=cmp_to_key(cmp))  # CPython AC, PyPy TLE
    words.sort(key=C)  # CPython/PyPy AC

    if N == 2:
        words[-1], words[-2] = words[-2], words[-1]
        print("".join(words))
        return

    for w1, w2 in pairwise(words):
        if w1 + w2 == w2 + w1:  # e.g. ab + abab = abab + ab
            print("".join(words))
            return

    words[-1], words[-2] = words[-2], words[-1]
    ans1 = "".join(words)
    words[-1], words[-2] = words[-2], words[-1]
    words[-2], words[-3] = words[-3], words[-2]
    ans2 = "".join(words)
    print(min(ans1, ans2))


if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

寫在最後

Cover Image Credit

The cover image was created by @floomf. All rights belong to the original artist.

It is used here only as a non-commercial cover illustration for this note. I do not claim ownership of the artwork.

If you are the copyright holder and believe this usage is inappropriate, please contact me by email or leave a comment. I will remove the image promptly.