在字符串处理和算法竞赛中我们常常会遇到一类问题给定一个字符串如何找到其所有循环同构串中字典序最小的那个这个问题在力扣周赛等算法竞赛中频繁出现例如经典的“最小表示法”问题。本文将深入浅出地讲解最小表示法的核心原理、实现细节并结合力扣周赛 511 中的相关题目提供从理论到实战的完整解决方案。无论你是正在准备算法面试的新手还是希望提升字符串处理能力的进阶开发者都能通过本文掌握这一高效算法的精髓并能在实际编码中灵活运用。1. 背景与核心概念1.1 什么是循环同构串对于一个长度为n的字符串s其循环同构串是指通过将s的前若干个字符移动到末尾或反之所得到的所有字符串。例如对于字符串“abcde”其循环同构串包括“abcde”、“bcdea”、“cdeab”、“deabc”、“eabcd”。这些字符串本质上是将原字符串首尾相接形成一个环从不同位置切开得到的结果。1.2 什么是最小表示法最小表示法顾名思义就是寻找一个字符串的所有循环同构串中字典序最小的那个表示。字典序比较类似于字符串在字典中的排列顺序逐字符比较 ASCII 码值。找到这个最小表示对于解决许多字符串匹配、循环比较问题至关重要因为它为所有循环等价的字符串提供了一个唯一的、可比较的“标准型”。1.3 为什么需要最小表示法唯一标识一组循环等价的字符串可以有无数种表示最小表示法提供了一个唯一的、确定性的代表便于进行哈希、比较和去重。高效比较判断两个字符串是否循环等价最朴素的方法是枚举其中一个字符串的所有循环移位与另一个比较时间复杂度为 O(n²)。而使用最小表示法可以在 O(n) 时间内将两个字符串都转化为其最小表示然后直接比较是否相等即可。算法竞赛高频考点在力扣周赛、Codeforces、ACM-ICPC 等算法竞赛中直接或间接考察最小表示法的题目屡见不鲜。掌握它是解决此类问题的关键。1.4 与相关概念的区别最小表示法 vs 字符串哈希字符串哈希可以快速比较子串但判断循环等价通常需要结合枚举或巧妙设计。最小表示法则直接针对循环等价问题提供了标准解。最小表示法 vs KMP算法KMP 主要用于单模匹配解决的是在一个文本串中查找一个模式串的问题。虽然思想有相通之处利用已匹配信息避免回溯但解决的问题不同。2. 算法原理与思路拆解最小表示法的核心思想是“双指针”“贪心比较”“跳过无效比较”。它能在 O(n) 的时间复杂度和 O(1) 的额外空间复杂度内解决问题。2.1 暴力法的局限最直接的想法是生成所有n个循环同构串然后找出字典序最小的。生成每个串需要 O(n) 时间比较字典序也需要 O(n)总时间复杂度为 O(n²)。当n很大时例如 10^5这种方法完全不可行。2.2 最小表示法破环成链为了便于处理我们通常将原字符串s复制一份连接到后面得到s s。这样从i开始长度为n的子串s[i:in]就对应了以i为起始位置的一个循环同构串。问题转化为在长度为2n的字符串ss中找到起始位置i(0 ≤ i n)使得子串s[i:in]的字典序最小。2.3 双指针算法流程我们使用两个指针i和j分别表示当前待比较的两个候选起始位置。再用一个变量k表示从这两个位置开始已经匹配的字符长度。初始化i 0,j 1,k 0。比较比较s[ik]和s[jk]在ss的范围内。如果s[ik] s[jk]则k继续比较下一个字符。如果s[ik] s[jk]说明从j开始的串字典序更大那么j以及j之后长度为k的串都不可能成为最小表示。我们可以将j向后跳跃到j k 1并将k重置为 0。如果s[ik] s[jk]说明从i开始的串字典序更大同理将i向后跳跃到i k 1并将k重置为 0。注意如果i和j在跳跃后变得相同需要将j以保证比较的是两个不同的位置。循环与终止重复步骤 2直到k n或i n或j n。此时min(i, j)就是最小表示的起始下标。算法精髓当s[ik] ! s[jk]时假设s[ik] s[jk]那么对于任意p(0 ≤ p ≤ k)以ip开头的串在比较到第k-p位时都会遇到s[ik]这个比s[jk]大的字符因此它们都不可能比以j开头的串更小。所以我们可以安全地将i跳到ik1从而跳过了大量无效的比较。这是算法达到 O(n) 复杂度的关键。3. 环境准备与代码框架为了清晰地演示算法我们使用 Python 作为实现语言。Python 语法简洁非常适合表达算法逻辑。读者也可以很容易地将其转换为 C、Java 等语言。环境要求Python 3.6 或更高版本。任意代码编辑器或 IDE如 VS Code, PyCharm。无需安装额外第三方库。示例项目结构 我们创建一个简单的 Python 脚本文件来封装算法并进行测试。min_lexicographic_rotation/ ├── min_representation.py # 算法实现 └── test_cases.py # 测试用例4. 完整算法实现与逐行解析下面我们给出最小表示法的标准实现并附上详细的注释。4.1 算法核心函数实现创建文件min_representation.pydef min_cyclic_string(s: str) - str: 返回字符串 s 的最小表示字典序最小的循环同构串。 参数: s (str): 输入字符串。 返回: str: 最小表示字符串。 n len(s) if n 0: return 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 else: if a b: # s[i]开头的串更大i跳到下一个可能的位置 i i k 1 else: # a b # s[j]开头的串更大j跳到下一个可能的位置 j j k 1 # 如果指针重合需要错开 if i j: j 1 # 重置已匹配长度 k 0 # 最小起始位置是 i 和 j 中较小的那个且未越界 start min(i, j) # 构造并返回最小表示 return s[start:] s[:start] def min_cyclic_string_index(s: str) - int: 返回字符串 s 的最小表示的起始下标。 参数: s (str): 输入字符串。 返回: int: 最小表示的起始下标 (0-indexed)。 n len(s) if n 0: return 0 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 else: if a b: i i k 1 else: j j k 1 if i j: j 1 k 0 return min(i, j)4.2 代码关键点解析破环成链的访问方式我们没有显式地构造ss而是通过取模操作(ik) % n来模拟在循环字符串上的访问。这节省了 O(n) 的空间。指针移动逻辑if a b: i i k 1是算法的核心。它利用了“贪心”和“跳过”的思想确保了时间复杂度为 O(n)。每次移动至少将指针i或j向前推进k1步而k的总增加量不超过n因此总循环次数是 O(n) 的。指针重合处理if i j: j 1。当两个指针指向同一位置时比较没有意义需要将其中一个向后移动一位。循环条件while i n and j n and k n。只要两个指针都没越界并且已匹配长度未达到整个字符串长度就继续比较。当k n时说明已经完整比较了一个周期此时min(i, j)即为答案。返回结果min_cyclic_string函数返回重构后的字符串而min_cyclic_string_index只返回起始下标。后者在只需要比较或哈希时更有用避免了字符串拼接的开销。5. 实战应用力扣周赛 511 例题分析虽然力扣周赛 511 的具体题目可能随时间变化但“最小表示法”通常用于解决诸如“判断两个字符串是否循环相等”、“寻找循环字符串的最小表示”等问题。我们以一个典型的虚拟题目为例进行讲解。题目描述模拟 给定两个字符串s和t判断它们是否循环等价。即能否通过将s循环移位若干次得到t。示例 1输入s abcde, t cdeab 输出true 解释s 循环左移 2 位得到 cdeab等于 t。示例 2输入s abcde, t abced 输出false5.1 解题思路最直接的思路是生成s的所有循环同构串看是否包含t时间复杂度 O(n²)。使用最小表示法我们可以将问题转化为比较s和t的最小表示是否相同。如果相同则它们循环等价否则不等价。5.2 代码实现基于我们上面实现的函数解法非常简单def are_cyclic_equivalent(s: str, t: str) - bool: 判断两个字符串是否循环等价。 if len(s) ! len(t): return False # 比较两者的最小表示是否相同 return min_cyclic_string(s) min_cyclic_string(t) # 更高效的版本避免构造字符串 def are_cyclic_equivalent_fast(s: str, t: str) - bool: 判断两个字符串是否循环等价高效版。 n len(s) if n ! len(t): return False # 获取 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 else: if a b: i i k 1 else: j j k 1 if i j: j 1 k 0 start_s min(i, j) # 获取 t 的最小表示起始下标 i, j, k 0, 1, 0 while i n and j n and k n: a t[(i k) % n] b t[(j k) % n] if a b: k 1 else: if a b: i i k 1 else: j j k 1 if i j: j 1 k 0 start_t min(i, j) # 比较从两个下标开始的 n 个字符是否完全相同 for d in range(n): if s[(start_s d) % n] ! t[(start_t d) % n]: return False return True5.3 复杂度分析时间复杂度O(n)。每个字符串求最小表示的过程是 O(n)最后比较 n 个字符也是 O(n)总复杂度为 O(n)。空间复杂度O(1)。只使用了几个整型变量。6. 测试与验证为了确保算法正确性我们需要设计全面的测试用例。创建test_cases.pyfrom min_representation import min_cyclic_string, min_cyclic_string_index, are_cyclic_equivalent, are_cyclic_equivalent_fast def test_min_representation(): test_cases [ (abcde, abcde), # 最小表示就是自身 (cdeab, abcde), # 循环移位 (aaaaa, aaaaa), # 全相同字符 (ababa, aaabb), # 需要计算最小是aabab 我们来验证 (, ), # 空字符串 (a, a), # 单字符 (ab, ab), # 双字符顺序已最小 (ba, ab), # 双字符需要旋转 ] print(测试 min_cyclic_string 和 min_cyclic_string_index:) for s, expected in test_cases: # 注意expected 这里是我们预先知道的最小表示字符串 # 对于像 ababa 这种我们需要先手动计算或信任算法 result_str min_cyclic_string(s) result_idx min_cyclic_string_index(s) reconstructed s[result_idx:] s[:result_idx] print(f输入: {s}) print(f 最小表示字符串: {result_str}) print(f 起始下标: {result_idx}) print(f 根据下标重构: {reconstructed}) assert result_str reconstructed, f重构不一致 print( ---) print(\n测试 are_cyclic_equivalent:) eq_test_cases [ (abcde, cdeab, True), (abcde, abcde, True), (a, a, True), (, , True), (abcde, abced, False), (ab, ba, True), # ab 和 ba 是循环等价的吗 ab循环移位得到ba (ab, abc, False), # 长度不同 ] for s, t, expected in eq_test_cases: result are_cyclic_equivalent(s, t) result_fast are_cyclic_equivalent_fast(s, t) print(f{s} vs {t}: 预期 {expected}, 结果 {result}, 快速版 {result_fast}) assert result expected and result_fast expected, f测试失败 # 随机测试 import random import string print(\n随机测试1000组...) for _ in range(1000): length random.randint(0, 50) chars .join(random.choices(string.ascii_lowercase, klength)) # 随机旋转 rotate random.randint(0, length-1) if length 0 else 0 rotated chars[rotate:] chars[:rotate] # 测试自身最小表示 mr min_cyclic_string(chars) idx min_cyclic_string_index(chars) assert mr chars[idx:] chars[:idx] # 测试循环等价 assert are_cyclic_equivalent(chars, rotated) True assert are_cyclic_equivalent_fast(chars, rotated) True # 测试与非等价串不等价大概率 if length 0: other .join(random.choices(string.ascii_lowercase, klength)) # 如果巧合相等跳过 if other ! chars and other ! rotated: # 这里不能断言一定为False因为随机可能生成循环等价的串但概率极低。 # 我们只检查算法是否一致 r1 are_cyclic_equivalent(chars, other) r2 are_cyclic_equivalent_fast(chars, other) assert r1 r2, f两个等价函数结果不一致: {chars}, {other} print(所有随机测试通过) if __name__ __main__: test_min_representation()运行测试脚本确保所有断言通过验证算法的正确性。7. 常见问题与排查思路在实际编码和解题中你可能会遇到以下问题问题现象常见原因解决思路算法陷入死循环或结果错误1. 指针移动逻辑写反和判断错误。2. 指针跳跃后未重置k0。3. 指针重合后未处理ij时未错开。4. 取模访问错误导致索引越界应使用(ik)%n。1. 仔细核对比较逻辑当s[ik] s[jk]时说明从i开始的串更大应移动i。可以记住口诀“谁大谁跳”。2. 确保每次发生字符不等时在移动i或j后立即执行k0。3. 在移动指针后立即检查if i j: j 1。4. 使用(index) % n来安全访问循环字符串。对于全相同字符的串如“aaaa”算法效率是否退化不会。虽然每次比较ab都会导致k直到kn循环结束。但i和j始终未移动循环只执行了n次比较时间复杂度仍是 O(n)。理解算法复杂度是O(n)的即使最坏情况全相同字符也是如此。如何证明算法一定能找到最小表示算法的正确性基于“字典序比较的传递性”和“跳过无效起始点的贪心策略”。形式化证明通常使用“反证法”和“不变量”。对于算法竞赛理解其“总是保留更优候选跳过劣质候选”的贪心思想即可。若要严格证明需参考算法导论或竞赛数学资料。算法返回的下标一定是唯一的吗如果字符串的最小表示有多个例如“abab”的最小表示可以是“abab”或“baba”它们字典序相同吗实际上“abab” “baba”那么算法返回的是最先找到的那个下标即i和j中较小的。对于字典序严格最小的表示其起始下标在循环同构串中是唯一的。注意当字符串由重复模式构成时可能存在多个位置得到相同的字符串。但算法返回的min(i, j)是符合算法流程的一个正确解。如何将其扩展到数组或数字序列算法不依赖于字符类型只依赖于元素间的比较操作,,。因此只需将输入从字符串改为列表比较操作从字符比较改为元素比较即可。实现一个泛型函数min_cyclic_representation(arr)其中arr可以是任何可比较对象的列表。8. 最佳实践与工程建议将最小表示法应用到实际项目或竞赛中时需要注意以下几点封装与复用像我们上面做的那样将算法封装成独立的函数如min_cyclic_string,min_cyclic_string_index。这样代码清晰便于测试和复用。注意边界条件始终处理空字符串 (len(s)0) 的情况避免取模运算除以零。性能考量在只需要比较是否循环等价而不需要具体最小表示字符串时使用min_cyclic_string_index结合逐字符比较避免不必要的字符串拼接Python 中字符串拼接有开销。对于极长的字符串例如长度超过 10^6确保使用 O(1) 的额外空间算法。我们的实现是满足的。扩展到其他数据结构该算法的思想可以推广到任何可以线性访问且具有全序关系的序列上比如整数数组、字节数组等。与字符串哈希结合在某些更复杂的问题中可能需要快速比较任意两个子串是否相等。这时可以先求出字符串的最小表示然后对其计算哈希值作为该循环等价类的唯一标识用于哈希表去重或快速比较。调试技巧如果对算法过程不理解可以添加详细的打印语句输出每一步i,j,k的值以及比较的字符手动模拟一个小例子如“bacac”的运行过程。变种问题最大表示法寻找字典序最大的循环同构串。只需将算法中的比较符号反转即可将a b时的移动逻辑与a b时互换。所有最小表示起始位置算法只返回一个。如果需要所有位置可以在找到第一个最小表示后利用字符串的周期性如果存在来找出所有位置这通常需要结合 KMP 算法求 next 数组。9. 总结与扩展学习最小表示法是一个经典且高效的字符串算法它巧妙地利用双指针和贪心策略在 O(n) 时间内解决了循环串的最小表示问题。掌握它不仅有助于解决力扣周赛中的特定题目更能提升你对字符串处理和双指针算法的理解深度。本文核心要点回顾问题定义找到字符串所有循环同构串中字典序最小的一个。算法核心双指针i,j配合匹配长度k通过比较s[ik]和s[jk]贪心地跳过不可能成为答案的起始位置。关键操作字符不等时较大的指针跳跃k1步并重置k0指针重合时需错开。复杂度时间 O(n)空间 O(1)。主要应用判断字符串循环等价、循环串去重、作为复杂问题的子过程。下一步学习建议在力扣上搜索相关题目尝试搜索 “circular string”、“rotation” 等关键词找到更多练习题巩固算法。学习相关算法KMP算法同样是利用已匹配信息避免回溯的典范用于字符串匹配。Z算法扩展KMP用于计算字符串每个后缀与自身的匹配长度与最小表示法有思想上的关联。后缀数组更强大的字符串数据结构可以解决包括最小表示法在内的更多问题通过将字符串复制拼接后求后缀数组。尝试实现最大表示法作为练习修改代码实现求最大字典序的循环表示。解决综合问题找一些将最小表示法作为其中一步的复杂题目例如某些计算几何问题最小表示法可用于处理循环序列或图论问题某些环的表示。算法能力的提升离不开反复的练习和思考。建议读者关闭本文后独立实现一遍代码并到力扣或其他在线判题系统上找到相关题目进行实战。遇到问题时再回来看文中的原理和注意事项相信你会有更深刻的体会。