如果你在力扣周赛里遇到一道字符串题，题目要求你判断两个循环字符串是否相等，或者找出一个字符串的最小字典序表示，你会怎么做？

很多人的第一反应可能是：把字符串复制一份拼接起来，然后枚举所有可能的起点，用substring截取并比较。这个思路直观，但时间复杂度是 O(n²)，当字符串长度达到 10⁵ 级别时，必然会超时。这正是力扣周赛 511 中一道题目的核心难点。

这道题考察的，是一个在字符串算法竞赛中经典，但在日常工程开发中鲜为人知的算法——最小表示法。它能在 O(n) 时间内，为一个循环字符串找到其所有循环同构串中字典序最小的那个。听起来很神奇？其实它的核心思想是“双指针贪心比较”，代码极其简洁，通常不超过 20 行。

本文将彻底拆解这个算法。我们不只告诉你“最小表示法是什么”，更重要的是讲清楚：

1. 为什么需要它？直接枚举法在力扣周赛里为什么行不通？
2. 它是如何工作的？双指针i和j是如何协作，一步步排除无效起点，最终锁定答案的？
3. 怎么写代码？我们会给出 Java、Python 等多种语言的模板，并逐行注释。
4. 有哪些坑？比如字符串所有字符都相同时的特殊情况如何处理？
5. 除了周赛，它还能用在哪？字符串匹配、数据去重等实际场景。

无论你是为了备战周赛，还是想深入理解字符串算法的精妙之处，这篇文章都将为你提供一份可直接“复制-粘贴-理解”的实战指南。

1. 这篇文章真正要解决的问题

在力扣周赛、牛客竞赛等编程比赛中，字符串处理是高频考点。有一类问题可以抽象为“循环同构串”的判断或查找。

什么是循环同构串？对于一个字符串s，将其首尾相接形成一个环，从任意位置开始、沿顺时针方向取出长度为n的字符串，都称为s的一个循环同构串。例如，字符串"abcd"的循环同构串包括"abcd","bcda","cdab","dabc"。

常见的题目形式：

1. 给定两个字符串，判断它们是否是循环同构的（即是否可以通过循环移位变得相同）。
2. 给定一个字符串，找出其所有循环同构串中字典序最小的一个（即“最小表示”）。
3. 基于最小表示法进行字符串哈希，用于快速比较或去重。

暴力法的瓶颈：最直观的解法是，对于长度为n的字符串，构造其双倍串s + s，然后枚举起始下标0到n-1，每次截取长度为n的子串进行比较。比较两个字符串是否相等需要 O(n) 时间，总时间复杂度为 O(n²)。当n较大时（例如力扣上常见的 10⁵），这个复杂度是无法接受的。

最小表示法的价值：最小表示法算法可以在O(n)时间内解决上述问题。它通过两个指针i和j，配合一个增量k，在比较过程中跳过大量不可能成为最小表示起点的位置，从而将时间复杂度从平方级降为线性级。理解并掌握这个算法，是解决此类周赛难题、提升竞赛排名的一个关键技巧。

2. 基础概念与核心原理

在深入代码之前，我们需要明确几个关键概念，并理解算法背后的贪心思想。

2.1 核心概念定义

• 循环字符串 (Cyclic String / Circular String)： 指首尾相连的字符串。在算法中，我们通常通过将原字符串s复制一份拼接成s + s来模拟其循环特性。
• 循环同构串 (Cyclic Isomorphism)： 如上所述，来源于同一个循环字符串的不同起点截取。
• 最小表示法 (Lexicographically Smallest Rotation / Minimum Representation)： 一个字符串的所有循环同构串中，字典序最小的那个。例如，"cbaa"的所有循环同构串有"cbaa","baac","aacb","acba"，其中最小的是"aacb"。
• 字典序比较： 像字典一样，从左到右逐个字符比较 ASCII 码。例如"abc"<"abd"，因为第三个字符'c'<'d'。

2.2 算法核心思想：双指针与贪心淘汰

算法的目标是找到最小表示的起始下标ans。

我们初始化两个指针i = 0,j = 1，它们代表两个待比较的候选起点。再初始化一个偏移量k = 0，表示从i和j开始，已经连续匹配了k个字符。

算法的核心过程是一个while循环，在i < n && j < n && k < n的条件下进行：

1. 比较字符s[(i+k) % n]和s[(j+k) % n]。
2. 如果它们相等 (==)，说明从i和j开始的前k+1个字符都一样，我们无法判断谁更优，于是k++，继续比较下一个字符。
3. 如果s[(i+k) % n]大于s[(j+k) % n]，这意味着从i开始的字符串在当前位置的字典序大于从j开始的。那么，以i为起点，以及i+1, i+2, ..., i+k这些点为起点的字符串，都不可能是最小表示。为什么？因为我们已经找到了一个比它们更小的候选j，并且在至少前k+1个字符上，j都不比i差（实际上在第k位更小）。因此，我们可以安全地将i直接跳到i + k + 1。同时，k重置为 0。
4. 同理，如果s[(i+k) % n]小于s[(j+k) % n]，则说明j及其后面一段不可能是最小表示，将j跳到j + k + 1，k重置为 0。
5. 这里有一个关键优化：如果i和j在跳转后重合了，我们让j++，以保证两个指针指向不同的起点进行比较。

当k达到n时，说明整个字符串都匹配上了，此时任意一个指针指向的起点都是最小表示（通常发生在字符串所有字符都相同时）。循环结束后，ans是i和j中的较小值。

为什么是 O(n)？每次比较 (s[i+k]vss[j+k])，无论结果如何，指针i或j都会至少向前移动一步（通过i += k+1或j += k+1）。而i和j都不会超过n，因此总的比较次数是 O(n) 级别的。

3. 环境准备与前置条件

本算法是纯逻辑算法，不依赖任何特定的库或框架。你只需要：

• 编程语言： 任何支持字符串操作和基础循环的语言均可。本文将以Java和Python为例进行演示，因为它们分别是力扣竞赛和日常开发中最常用的语言之一。
• 一个可以运行代码的环境： 力扣的在线判题系统、本地的 IDE（如 IntelliJ IDEA, VS Code, PyCharm）或简单的文本编辑器配合命令行均可。
• 对字符串和数组的基本操作： 了解如何访问字符串中的字符（注意 Java 中用charAt()，Python 中可直接索引）。

4. 核心流程拆解

让我们将上一节的思想转化为清晰的步骤。

输入： 一个字符串s，长度为n。输出： 该字符串最小表示的起始下标ans。

算法步骤：

1. 初始化：

   • n = s.length()
   • i = 0,j = 1,k = 0
   • ans暂不需要，最后取min(i, j)

2. 主循环： 当i < n && j < n && k < n时，重复步骤 3-6。

3. 字符比较：

   • 计算a = s[(i + k) % n]
   • 计算b = s[(j + k) % n]

4. 情况一：字符相等(a == b)：

   • 说明当前比较的两个候选序列在前k+1位都相同，无法决出胜负。
   • 操作：k++，继续比较下一位。

5. 情况二：i序列更大(a > b)：

   • 说明从j开始的序列在当前位更小，i及其后面连续k个起点都不可能是答案。
   • 操作：i = i + k + 1。如果i == j，则i++（避免指针重合）。k = 0（重置匹配长度）。

6. 情况三：j序列更大(a < b)：

   • 说明从i开始的序列在当前位更小，j及其后面连续k个起点都不可能是答案。
   • 操作：j = j + k + 1。如果i == j，则j++。k = 0。

7. 循环结束与结果返回：

   • 循环终止条件之一是k == n，这意味着整个字符串从i和j开始完全一致，通常发生在字符串所有字符相同的情况下。此时i和j都可能是答案，取min(i, j)即可。
   • 另一个终止条件是i >= n或j >= n，这不会在正常流程中发生，因为指针跳跃不会超过n。最终答案同样是min(i, j)。

5. 完整示例与代码实现

下面我们给出 Java 和 Python 的完整实现模板。这些模板可以直接用于解决力扣上“判断循环字符串是否相等”或“寻找最小表示”的问题。

5.1 Java 实现

public class MinimumRepresentation { /** * 返回字符串 s 的最小表示的起始索引 * @param s 输入字符串 * @return 最小表示的起始下标 (0-based) */ public static int minRepresentation(String s) { if (s == null || s.length() == 0) { return 0; } int n = s.length(); int i = 0, j = 1, k = 0; while (i < n && j < n && k < n) { char a = s.charAt((i + k) % n); char b = s.charAt((j + k) % n); if (a == b) { k++; } else if (a > b) { // s[i...] 的字典序大于 s[j...]，i 到 i+k 都不可能为答案 i = i + k + 1; if (i == j) { i++; // 保证 i 和 j 不同 } k = 0; // 重置匹配长度 } else { // a < b // s[j...] 的字典序大于 s[i...]，j 到 j+k 都不可能为答案 j = j + k + 1; if (i == j) { j++; } k = 0; } } // 循环结束，答案是两个指针中的较小者 return Math.min(i, j); } /** * 获取字符串 s 的最小表示字符串 * @param s 输入字符串 * @return 最小表示字符串 */ public static String getMinRepresentationString(String s) { int idx = minRepresentation(s); int n = s.length(); // 利用 substring 构造最小表示字符串 return s.substring(idx) + s.substring(0, idx); } // 测试代码 public static void main(String[] args) { String test1 = "cbaa"; String test2 = "abca"; String test3 = "aaaa"; // 全相同字符 System.out.println("测试字符串: \"" + test1 + "\""); System.out.println("最小表示起始索引: " + minRepresentation(test1)); System.out.println("最小表示字符串: \"" + getMinRepresentationString(test1) + "\""); System.out.println(); System.out.println("测试字符串: \"" + test2 + "\""); System.out.println("最小表示起始索引: " + minRepresentation(test2)); System.out.println("最小表示字符串: \"" + getMinRepresentationString(test2) + "\""); System.out.println(); System.out.println("测试字符串: \"" + test3 + "\""); System.out.println("最小表示起始索引: " + minRepresentation(test3)); System.out.println("最小表示字符串: \"" + getMinRepresentationString(test3) + "\""); } }

代码关键点解析：

1. s.charAt((i + k) % n)： 通过取模运算% n来模拟循环访问，避免了实际构造双倍字符串s+s的空间开销。
2. if (i == j) { i++; }： 这是关键细节。当指针跳转后重合，必须让其中一个指针前进一位，否则比较会陷入死循环（自己和自己比，永远相等）。
3. Math.min(i, j)： 循环结束时，i和j至少有一个是有效答案。取较小者是为了保证索引在[0, n)范围内（在循环中，i或j有可能因为+k+1而暂时等于n，但循环条件会终止）。

5.2 Python 实现

Python 的实现更加简洁，利用了 Python 字符串可索引和负数索引的特性（但在最小表示法核心逻辑中，我们依然使用取模来保持通用性）。

def min_representation(s: str) -> int: """ 返回字符串 s 的最小表示的起始索引 :param s: 输入字符串 :return: 最小表示的起始下标 (0-based) """ if not s: return 0 n = len(s) i, j, k = 0, 1, 0 while i < n and j < n and k < n: a = s[(i + k) % n] b = s[(j + k) % n] if a == b: k += 1 elif a > b: # s[i...] 的字典序大于 s[j...] i = i + k + 1 if i == j: i += 1 k = 0 else: # a < b # s[j...] 的字典序大于 s[i...] j = j + k + 1 if i == j: j += 1 k = 0 # 返回较小的索引 return min(i, j) def get_min_representation_string(s: str) -> str: """ 获取字符串 s 的最小表示字符串 :param s: 输入字符串 :return: 最小表示字符串 """ idx = min_representation(s) n = len(s) # 利用切片构造最小表示字符串 return s[idx:] + s[:idx] if __name__ == "__main__": test_cases = ["cbaa", "abca", "aaaa", "bcab"] for test in test_cases: idx = min_representation(test) min_str = get_min_representation_string(test) print(f"测试字符串: \"{test}\"") print(f"最小表示起始索引: {idx}") print(f"最小表示字符串: \"{min_str}\"") print()

Python 实现的注意点：

1. 逻辑与 Java 版完全一致。
2. Python 中字符串索引s[i]是 O(1) 操作。
3. 构造最小表示字符串时，s[idx:] + s[:idx]的切片操作非常高效和直观。

6. 运行结果与效果验证

运行上述 Java 或 Python 的测试代码，你会得到类似以下的输出：

测试字符串: "cbaa" 最小表示起始索引: 2 最小表示字符串: "aacb" 测试字符串: "abca" 最小表示起始索引: 0 最小表示字符串: "abca" 测试字符串: "aaaa" 最小表示起始索引: 0 最小表示字符串: "aaaa" 测试字符串: "bcab" 最小表示起始索引: 1 最小表示字符串: "abbc"

如何验证结果的正确性？

1. 手动枚举：对于短字符串，可以手动列出其所有循环同构串，找出字典序最小的，看是否与程序输出一致。例如"cbaa"：
   • 0: cbaa
   • 1: baac
   • 2: aacb← 最小
   • 3: acba程序输出索引 2，字符串"aacb"，正确。
2. 使用暴力法对照：写一个 O(n²) 的暴力算法，对小规模数据（n <= 1000）进行随机测试，与最小表示法的结果对比，确保一致。
3. 在力扣上提交：寻找相关的题目（例如 LeetCode 796. 旋转字符串，或者一些周赛题目），用这个算法模板提交，看是否能通过所有测试用例。

复杂度验证：你可以尝试用这个算法处理一个长度为 10⁶ 的随机字符串。O(n) 的算法会在毫秒级完成，而 O(n²) 的暴力算法将完全无法运行。这是算法效率最直接的证明。

7. 常见问题与排查思路

在实现和使用最小表示法时，你可能会遇到以下问题：

8. 最佳实践与工程建议

虽然最小表示法代码很短，但在工程应用和竞赛中，遵循一些最佳实践能让代码更健壮、更高效。

1. 封装成工具函数： 如上面的代码所示，将min_representation和get_min_representation_string封装成独立的函数。在解决具体问题时，直接调用即可，避免重复编写和出错。

2. 处理空串和单字符串： 在函数开头添加边界检查。对于空串，可以返回 0 或 -1（根据约定）。对于单字符串，算法也能正确工作，但显式处理可以使逻辑更清晰。

3. 空间复杂度优化： 我们的实现是 O(1) 额外空间的，因为我们使用了取模运算，没有复制字符串。这是最优的。不要为了“方便”而先构造s + s，那样会使用 O(n) 的额外空间。

4. 与字符串哈希结合： 在需要频繁比较两个字符串的循环同构关系，或者需要对大量字符串的最小表示进行去重时，可以先求出每个字符串的最小表示，然后计算这个最小表示的哈希值（如多项式滚动哈希）。用哈希值进行比较或存入哈希集合，效率极高。

   # 示例：使用最小表示法进行字符串循环同构去重 def normalize_string(s: str) -> str: idx = min_representation(s) n = len(s) return s[idx:] + s[:idx] string_list = ["abc", "bca", "cab", "acb", "cba", "bac"] unique_representations = set() for s in string_list: unique_representations.add(normalize_string(s)) print(unique_representations) # 输出：{'abc', 'acb'} (前三个是循环同构，后三个是循环同构)

5. 理解算法局限性： 最小表示法解决的是精确匹配问题。对于允许有容错（如编辑距离）的模糊匹配场景，它不适用。它的核心是比较字典序。

6. 在力扣周赛中的策略：

   • 识别题型： 题目描述中出现“循环”、“旋转”、“是否可以通过旋转得到”等关键词，并且数据范围较大（n 可达 10^5），应立刻想到最小表示法。
   • 模板化： 将代码模板保存在本地，比赛时快速复制粘贴，稍作修改即可。
   • 测试用例： 务必测试全相同字符、升序、降序等边界情况。

7. 扩展：最大表示法： 只需将代码中的比较符号反转即可。寻找字典序最大的循环同构串，把a > b和a < b分支的处理逻辑对调。

   // 最大表示法 Java 片段 if (a == b) { k++; } else if (a < b) { // 注意这里：当 a < b 时，说明 s[i...] 更小，淘汰 i i = i + k + 1; if (i == j) i++; k = 0; } else { // a > b j = j + k + 1; if (i == j) j++; k = 0; }

掌握最小表示法，不仅仅是学会了一个算法模板，更是掌握了一种利用已有信息跳过无效状态的贪心优化思想。这种思想在 KMP、Z-algorithm 等字符串算法中也有体现。下次在周赛或面试中遇到循环字符串问题，你可以自信地写出那个简洁高效的 O(n) 解法了。