最小表示法：O(n)时间解决循环字符串字典序问题

1. 先搞清楚“最小表示法”到底在解决什么问题

如果你在力扣周赛里遇到字符串旋转、循环同构这类题目，或者看到“最小表示法”这个词有点懵，那这篇文章就是为你准备的。它不是什么高深莫测的算法，而是一个解决特定字符串比较问题的高效工具。简单说，它要解决的是：给你一个字符串，比如“bcdea”，你可以把它循环移位，得到“cdeab”、“deabc”等等。那么，在所有可能的循环移位字符串中，字典序最小的那个是哪一个？这就是“最小表示法”要找到的答案。

为什么力扣周赛会考这个？因为它能把一个看起来需要 O(n²) 暴力比较的问题，优化到 O(n) 的时间复杂度。在周赛那种分秒必争的环境下，知道这个算法，可能就是你能否 AC 的关键。它特别适合处理那些字符串首尾相连、形成环的场景，比如判断两个环状字符串是否“本质相同”。

所以，这篇文章不讲空泛的理论，直接带你拆解最小表示法的核心思想、标准实现、力扣实战变形以及避坑要点。目标是让你看完后，不仅能写出代码，更能理解为什么这么写，以及下次在周赛或笔试中遇到类似问题，能立刻反应过来该用它。

2. 理解核心思想：为什么能比暴力法快那么多

在动手写代码前，必须理解算法为什么有效。这是避免死记硬背模板、能在不同题目中灵活运用的关键。

2.1 暴力法的瓶颈在哪里？

最直接的想法是：生成字符串 S 所有 n 个循环同构串（n 为字符串长度），然后逐个比较，找出字典序最小的。生成每个串需要 O(n)，比较两个串最坏也需要 O(n)，总复杂度就是 O(n²)。当 n 达到 10^5 级别时，这显然会超时。

2.2 最小表示法的优化思路：利用“已经比较过的信息”

最小表示法的聪明之处在于，它不生成所有字符串，而是用两个指针i和j在原字符串上模拟比较过程，并利用比较结果直接跳过大量不可能成为答案的起始位置。

它的核心过程可以概括为：

1. 初始化两个指针i=0,j=1，和一个用于比较的偏移量k=0。
2. 比较S[i+k]和S[j+k]：
   • 如果相等，k++，继续比较下一位。
   • 如果S[i+k] > S[j+k]，说明从i开始的串字典序比从j开始的大。那么，对于i到i+k这个区间内的所有位置作为起点，都不可能成为最小表示（因为j开头的串已经在某一位更小了）。所以我们可以直接将i跳到i+k+1。
   • 如果S[i+k] < S[j+k]，同理，说明j开头的串更大，将j跳到j+k+1。
3. 如果跳转后i和j相同，则让其中一个指针向后移动一位（避免比较同一个串）。
4. 当i或j超出字符串长度，或者k等于长度n时，算法结束。此时min(i, j)就是最小表示的起始下标。

为什么这样跳转是安全的？这是算法的精髓。当我们在第k位发现S[i+k] > S[j+k]时，意味着对于任意p (0 <= p <= k)，以i+p开头的串，其字典序都会大于以j+p开头的串（因为前p-1位相等，第p位决定了大小）。因此，i到i+k整个区间都可以被安全地跳过。这个“跳过”操作是算法达到 O(n) 复杂度的根本原因，因为每个位置最多被比较和跳过一次。

2.3 一个简单的例子走一遍

以字符串S = “bcdea”为例，我们手动走一下流程，理解指针是如何跳动的。

1. i=0(‘b’), j=1(‘c’), k=0。比较 S[0]=‘b’ 和 S[1]=‘c’，‘b’ < ‘c’。所以 j 需要跳到 j+k+1 = 2。
2. i=0(‘b’), j=2(‘d’), k=0。比较 ‘b’ 和 ‘d’，‘b’ < ‘d’。j 跳到 3。
3. i=0(‘b’), j=3(‘e’), k=0。比较 ‘b’ 和 ‘e’，‘b’ < ‘e’。j 跳到 4。
4. i=0(‘b’), j=4(‘a’), k=0。比较 ‘b’ 和 ‘a’，‘b’ > ‘a’。这次是 i 更大，所以 i 跳到 i+k+1 = 1。
5. i=1(‘c’), j=4(‘a’)。此时 i != j，重置 k=0。比较 ‘c’ 和 ‘a’，‘c’ > ‘a’。i 跳到 2。
6. i=2(‘d’), j=4(‘a’)。比较 ‘d’ 和 ‘a’，‘d’ > ‘a’。i 跳到 3。
7. i=3(‘e’), j=4(‘a’)。比较 ‘e’ 和 ‘a’，‘e’ > ‘a’。i 跳到 4。
8. 现在 i=4, j=4，两者相等。根据规则，将 j 加一变为 5（已等于 n，结束循环）。
9. 最终，min(i, j) = 4。从下标4开始的串是“a”，拼接原串前半部分得到“abcde”，这确实是所有循环同构串中字典序最小的。

通过这个过程，你可以看到指针i和j是如何快速移动，避免了许多不必要的比较。

3. 标准模板代码与逐行解析

理解了思想，我们来看具体实现。下面给出最小表示法求字符串S最小表示起始下标的C++ 标准模板。我建议你先理解，然后自己默写，而不是直接复制。

int minRepresentation(string s) { int n = s.length(); int i = 0, j = 1, k = 0; while (i < n && j < n && k < n) { char a = s[(i + k) % n]; char b = s[(j + k) % n]; if (a == b) { k++; } else { if (a > b) { i = i + k + 1; } else { j = j + k + 1; } if (i == j) { i++; // 或者 j++，保证两个指针不同 } k = 0; // 重置比较长度 } } return min(i, j); }

关键点逐行解析：

1. 循环条件while (i < n && j < n && k < n)：

   • i < n && j < n确保两个指针都在有效范围内。
   • k < n是核心限制。k表示当前已匹配的长度。如果k等于n，说明已经完整地比较了整个循环串，两个表示完全相等，此时可以直接结束。

2. 取字符s[(i + k) % n]：

   • 使用% n是为了模拟循环字符串。当i+k超过字符串末尾时，自动绕回到开头。这是处理“循环”特性的关键。

3. 比较分支if (a == b)：

   • 相等则k++，继续比较下一位。

4. 比较分支else：

   • 如果a > b，说明从i开始的串更大。根据前面讲的原理，i到i+k的区间都可以跳过，所以i = i + k + 1。
   • 如果a < b，则对j进行类似操作：j = j + k + 1。

5. 指针重合处理if (i == j)：

   • 如果跳转后i和j指向了同一个位置，那么它们就是在比较同一个起点，没有意义。所以需要将其中一个指针向后移动一位。这里让i++或j++都可以。

6. 重置k = 0：

   • 只要发生了不相等的情况并进行了指针跳转，之前匹配的长度k就作废了，需要从头 (k=0) 开始新的比较。

7. 返回值return min(i, j)：

   • 循环结束时，i和j至少有一个超过了n或者k==n。未越界的那个指针（或者两者中较小的那个）就是最小表示的起始下标。因为算法保证了失败指针会向后跳，所以未越界的指针就是答案。

复杂度分析： 每个指针i和j都只会单调递增，每个字符最多被比较两次（一次作为a，一次作为b），因此时间复杂度是严格的O(n)，空间复杂度为O(1)。

4. 在力扣周赛中的典型应用与变形

掌握了模板，我们来看看它在力扣题目中怎么用。力扣不会直接出“求最小表示”的裸题，而是会把它包装在更大的问题里。

4.1 经典应用：判断两个字符串是否循环同构

这是最小表示法最直接的应用。题目可能这样描述：给定两个字符串A和B，判断它们是否可以通过循环移位变得相同。

解题思路：

1. 分别求出A和B的最小表示法起始下标startA和startB。
2. 根据起始下标，构造出它们的最小表示字符串minA和minB。

   string getMinRep(string s) { int start = minRepresentation(s); return s.substr(start) + s.substr(0, start); } bool isCyclicIsomorphic(string A, string B) { if (A.length() != B.length()) return false; return getMinRep(A) == getMinRep(B); }

3. 比较minA和minB是否相等。相等则说明循环同构。

为什么这样做是对的？因为循环同构的字符串，它们的最小表示是唯一的。如果两个串循环同构，它们的最小表示必然相同；反之，如果最小表示相同，则它们必然循环同构。

4.2 周赛变形题举例：拼接形成最小字典序大字符串

假设题目是：给你一个字符串数组，你需要将它们以某种顺序拼接起来，形成一个大的环状字符串（即首尾也视为相连），使得这个环状字符串的字典序最小。

暴力思路：枚举所有排列，对每个排列形成的环求最小表示，再比较。复杂度是阶乘级，不可行。

结合最小表示法的思路：

1. 这其实是一个排序问题。我们需要定义一种比较两个字符串X和Y的规则，来决定在最终环中，X应该放在Y前面还是后面。
2. 比较规则不是简单的X < Y，因为X和Y在环中相邻时，接口处的字符会影响整体字典序。一种常见的有效规则是：比较X+Y和Y+X的字典序。但这对于环来说还不够。
3. 更贴近本题的规则是：将X和Y分别视为一个环，求出它们的最小表示minX和minY。然后直接比较minX和minY。
4. 按照这个规则对字符串数组进行排序，然后将排序后的字符串直接拼接起来。最后，对这个拼接后的大字符串再求一次最小表示，作为最终输出的起点。

核心逻辑：

string makeLargestCyclicString(vector<string>& strs) { // 1. 自定义排序：比较两个字符串的最小表示 sort(strs.begin(), strs.end(), [](const string& a, const string& b) { return getMinRep(a) < getMinRep(b); }); // 2. 拼接 string total; for (auto& s : strs) total += s; // 3. 对总字符串求最小表示作为输出起点 int start = minRepresentation(total); return total.substr(start) + total.substr(0, start); }

注意：这只是一个思路框架，具体题目可能需要微调比较规则（比如相等时的处理）或拼接后的处理方式。但“利用最小表示法来定义环的字典序”这个核心思想是通用的。

4.3 处理带数字的字符串或数组

最小表示法不仅适用于字符，也适用于数字数组。力扣上有些题目是关于循环数组的，比如找循环数组的某个特征位置。这时，只需要把模板中的char比较改成int比较即可。

示例：寻找循环数组的最小表示（数字版）

int minRepresentation(vector<int>& nums) { int n = nums.size(); int i = 0, j = 1, k = 0; while (i < n && j < n && k < n) { int a = nums[(i + k) % n]; int b = nums[(j + k) % n]; if (a == b) { k++; } else { if (a > b) { i = i + k + 1; } else { j = j + k + 1; } if (i == j) i++; k = 0; } } return min(i, j); }

5. 实战避坑指南与调试技巧

模板看似简单，但在实际编码，尤其是周赛紧张环境下，容易出错。下面是我总结的几个关键避坑点和调试方法。

5.1 常见错误与修正

1. 忘记处理指针重合：这是最容易遗漏的点。在i或j跳转后，必须检查if (i == j)，并让其中一个加1。否则，如果两者重合，循环会陷入无意义的自比较，k会一直增加直到等于n，虽然结果可能对，但逻辑不严谨，且在有些变形题中会导致错误。

2. 循环条件写错：标准的while条件应该是(i < n && j < n && k < n)。绝对不能写成(k < n)，因为i或j可能已经越界，导致数组访问出错。也不能漏掉k < n，否则当两个表示完全相同时，k会一直增加，造成死循环。

3. 跳转后忘记重置k：在a != b的分支里，执行完i或j的跳转后，必须将k重置为0。因为新的i和j位置需要从头开始比较。

4. 返回值的误解：函数返回的是最小表示在原串中的起始下标，而不是最小表示字符串本身。你需要用s.substr(ret) + s.substr(0, ret)来得到字符串。

5.2 调试技巧：用简单例子验证

在写完代码后，不要直接用复杂用例测试。我习惯用以下几个简单但具有代表性的例子来快速验证：

• 单字符串：“a”。结果应为0。
• 全相同串：“aaaa”。结果应为0。这个用例专门测试k==n的终止条件。
• 最小表示在中间的串：“bcdea”（如上例），结果应为4。
• 有重复前缀的串：“abab”。它的循环同构有“abab”,“baba”,“abab”,“baba”。最小表示是“abab”，起始下标为0。这个用例测试指针跳转逻辑。
• 另一个有重复前缀的串：“babab”。最小表示是“ababb”，起始下标需要计算。

在调试时，可以在while循环内打印i, j, k, a, b的值，对照手动推导的过程，看算法是否按预期运行。

5.3 性能与边界考量

• 时间复杂度：O(n) 已经足够优秀，对于力扣常见的 10^5 数据范围绰绰有余。
• 空间复杂度：O(1)，仅用了几个指针变量。
• 字符串长度：注意题目是否说明字符串非空。我们的模板假设n > 0。如果可能为空，需要在函数开始处判断if (s.empty()) return 0;或根据题目要求返回-1等。
• 字符集：模板适用于任何可比较的数据类型（char, int等）。

6. 与其他方法的对比及选用场景

知道什么时候用最小表示法，和会写代码一样重要。

6.1 对比暴力枚举法

结论：只要问题规模可能变大，暴力法就不可行。最小表示法是解决循环字符串字典序问题的标准算法。

6.2 对比“字符串哈希+二分”法

还有一种常见思路是字符串哈希+二分查找。我们可以枚举每个起始位置i，然后用哈希在 O(logn) 时间内比较两个循环串的字典序大小，从而在 O(n log n) 内找到最小表示。

结论：在力扣周赛环境中，最小表示法是更优选择。它更快、更省空间，且没有哈希冲突的担忧，代码也更简洁。字符串哈希法更通用，可以解决更多类型的子串比较问题，但针对“最小表示”这个特定问题，杀鸡无需牛刀。

6.3 何时应该想到使用最小表示法？

当你看到题目中出现以下关键词时，就该警觉了：

• “循环” (Cyclic)
• “旋转” (Rotation)
• “同构” (Isomorphic)，且特指循环同构
• “首尾相连”
• “字典序最小/最大的循环表示”
• 问题本质是在一个环上找某个特征起点

力扣周赛第511场考察这个算法，很可能就是把上述某个关键词包装在了题目描述里。平时刷题时，可以在“字符串”和“模拟”分类下找相关题目练习，培养题感。

7. 总结与下一步练习建议

最小表示法是一个典型的“思想巧妙、代码简短、效率极高”的竞赛算法。它的核心价值在于，将看似需要平方级复杂度的问题，通过指针跳跃比较降到了线性复杂度。

要真正掌握它，我的建议是：

1. 理解优先于记忆：务必搞懂i,j,k三个指针的含义，以及为什么指针可以安全地大跨度跳跃。自己用“abab”、“bcdea”这样的例子在纸上画一遍。
2. 熟练默写模板：在理解的基础上，把 C++ 模板代码写熟练，做到5分钟内无错写出。注意检查指针重合和k的重置。
3. 识别问题变形：在力扣上搜索“循环字符串”、“旋转字符串”相关题目，尝试用最小表示法解决。不仅做裸题，更要思考如何将它作为子过程，嵌入到更复杂的问题中（比如第4.2节提到的排序拼接问题）。
4. 对比学习：了解字符串哈希法，明白它的原理和适用场景，这样你就能在两者间做出正确选择。

最后，在周赛实战中，如果遇到相关题目，先想清楚再写。花2分钟确认是否真的适用最小表示法，比写了一半发现思路错误再重写要节省得多。把这个算法放进你的“算法工具箱”，下次遇到环状字符串的字典序问题，你就能从容应对了。