时间解决循环字符串字典序比较的算法精讲)
如果你在力扣周赛里遇到一道字符串题题目要求你判断两个循环字符串是否相等或者找出一个字符串的最小字典序表示你会怎么做很多人的第一反应可能是把字符串复制一份拼接起来然后枚举所有可能的起点用substring截取并比较。这个思路直观但时间复杂度是 O(n²)当字符串长度达到 10⁵ 级别时必然会超时。这正是力扣周赛 511 中一道题目的核心难点。这道题考察的是一个在字符串算法竞赛中经典但在日常工程开发中鲜为人知的算法——最小表示法。它能在 O(n) 时间内为一个循环字符串找到其所有循环同构串中字典序最小的那个。听起来很神奇其实它的核心思想是“双指针贪心比较”代码极其简洁通常不超过 20 行。本文将彻底拆解这个算法。我们不只告诉你“最小表示法是什么”更重要的是讲清楚为什么需要它直接枚举法在力扣周赛里为什么行不通它是如何工作的双指针i和j是如何协作一步步排除无效起点最终锁定答案的怎么写代码我们会给出 Java、Python 等多种语言的模板并逐行注释。有哪些坑比如字符串所有字符都相同时的特殊情况如何处理除了周赛它还能用在哪字符串匹配、数据去重等实际场景。无论你是为了备战周赛还是想深入理解字符串算法的精妙之处这篇文章都将为你提供一份可直接“复制-粘贴-理解”的实战指南。1. 这篇文章真正要解决的问题在力扣周赛、牛客竞赛等编程比赛中字符串处理是高频考点。有一类问题可以抽象为“循环同构串”的判断或查找。什么是循环同构串对于一个字符串s将其首尾相接形成一个环从任意位置开始、沿顺时针方向取出长度为n的字符串都称为s的一个循环同构串。例如字符串abcd的循环同构串包括abcd,bcda,cdab,dabc。常见的题目形式给定两个字符串判断它们是否是循环同构的即是否可以通过循环移位变得相同。给定一个字符串找出其所有循环同构串中字典序最小的一个即“最小表示”。基于最小表示法进行字符串哈希用于快速比较或去重。暴力法的瓶颈最直观的解法是对于长度为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 码。例如abcabd因为第三个字符cd。2.2 算法核心思想双指针与贪心淘汰算法的目标是找到最小表示的起始下标ans。我们初始化两个指针i 0,j 1它们代表两个待比较的候选起点。再初始化一个偏移量k 0表示从i和j开始已经连续匹配了k个字符。算法的核心过程是一个while循环在i n j n k n的条件下进行比较字符s[(ik) % n]和s[(jk) % n]。如果它们相等 ()说明从i和j开始的前k1个字符都一样我们无法判断谁更优于是k继续比较下一个字符。如果s[(ik) % n]大于s[(jk) % n]这意味着从i开始的字符串在当前位置的字典序大于从j开始的。那么以i为起点以及i1, i2, ..., ik这些点为起点的字符串都不可能是最小表示。为什么因为我们已经找到了一个比它们更小的候选j并且在至少前k1个字符上j都不比i差实际上在第k位更小。因此我们可以安全地将i直接跳到i k 1。同时k重置为 0。同理如果s[(ik) % n]小于s[(jk) % n]则说明j及其后面一段不可能是最小表示将j跳到j k 1k重置为 0。这里有一个关键优化如果i和j在跳转后重合了我们让j以保证两个指针指向不同的起点进行比较。当k达到n时说明整个字符串都匹配上了此时任意一个指针指向的起点都是最小表示通常发生在字符串所有字符都相同时。循环结束后ans是i和j中的较小值。为什么是 O(n)每次比较 (s[ik]vss[jk])无论结果如何指针i或j都会至少向前移动一步通过i k1或j k1。而i和j都不会超过n因此总的比较次数是 O(n) 级别的。3. 环境准备与前置条件本算法是纯逻辑算法不依赖任何特定的库或框架。你只需要编程语言 任何支持字符串操作和基础循环的语言均可。本文将以Java和Python为例进行演示因为它们分别是力扣竞赛和日常开发中最常用的语言之一。一个可以运行代码的环境 力扣的在线判题系统、本地的 IDE如 IntelliJ IDEA, VS Code, PyCharm或简单的文本编辑器配合命令行均可。对字符串和数组的基本操作 了解如何访问字符串中的字符注意 Java 中用charAt()Python 中可直接索引。4. 核心流程拆解让我们将上一节的思想转化为清晰的步骤。输入 一个字符串s长度为n。输出 该字符串最小表示的起始下标ans。算法步骤初始化n s.length()i 0,j 1,k 0ans暂不需要最后取min(i, j)主循环 当i n j n k n时重复步骤 3-6。字符比较计算a s[(i k) % n]计算b s[(j k) % n]情况一字符相等(a b)说明当前比较的两个候选序列在前k1位都相同无法决出胜负。操作k继续比较下一位。情况二i序列更大(a b)说明从j开始的序列在当前位更小i及其后面连续k个起点都不可能是答案。操作i i k 1。如果i j则i避免指针重合。k 0重置匹配长度。情况三j序列更大(a b)说明从i开始的序列在当前位更小j及其后面连续k个起点都不可能是答案。操作j j k 1。如果i j则j。k 0。循环结束与结果返回循环终止条件之一是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 到 ik 都不可能为答案 i i k 1; if (i j) { i; // 保证 i 和 j 不同 } k 0; // 重置匹配长度 } else { // a b // s[j...] 的字典序大于 s[i...]j 到 jk 都不可能为答案 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) \); } }代码关键点解析s.charAt((i k) % n) 通过取模运算% n来模拟循环访问避免了实际构造双倍字符串ss的空间开销。if (i j) { i; } 这是关键细节。当指针跳转后重合必须让其中一个指针前进一位否则比较会陷入死循环自己和自己比永远相等。Math.min(i, j) 循环结束时i和j至少有一个是有效答案。取较小者是为了保证索引在[0, n)范围内在循环中i或j有可能因为k1而暂时等于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 实现的注意点逻辑与 Java 版完全一致。Python 中字符串索引s[i]是 O(1) 操作。构造最小表示字符串时s[idx:] s[:idx]的切片操作非常高效和直观。6. 运行结果与效果验证运行上述 Java 或 Python 的测试代码你会得到类似以下的输出测试字符串: cbaa 最小表示起始索引: 2 最小表示字符串: aacb 测试字符串: abca 最小表示起始索引: 0 最小表示字符串: abca 测试字符串: aaaa 最小表示起始索引: 0 最小表示字符串: aaaa 测试字符串: bcab 最小表示起始索引: 1 最小表示字符串: abbc如何验证结果的正确性手动枚举对于短字符串可以手动列出其所有循环同构串找出字典序最小的看是否与程序输出一致。例如cbaa0: cbaa1: baac2: aacb← 最小3: acba程序输出索引 2字符串aacb正确。使用暴力法对照写一个 O(n²) 的暴力算法对小规模数据n 1000进行随机测试与最小表示法的结果对比确保一致。在力扣上提交寻找相关的题目例如 LeetCode 796. 旋转字符串或者一些周赛题目用这个算法模板提交看是否能通过所有测试用例。复杂度验证你可以尝试用这个算法处理一个长度为 10⁶ 的随机字符串。O(n) 的算法会在毫秒级完成而 O(n²) 的暴力算法将完全无法运行。这是算法效率最直接的证明。7. 常见问题与排查思路在实现和使用最小表示法时你可能会遇到以下问题问题现象可能原因排查方式解决方案程序陷入死循环指针i和j在跳转后重合且没有处理。检查if (a b)和else分支中在更新i或j后是否添加了if (i j) { i; }或类似逻辑。确保在指针跳转后如果i j则让其中一个指针向前移动一位。结果索引不正确对于全相同字符的串循环结束时i或j可能等于n因为i i k 1且k可能接近n。在循环结束后打印i和j的值。对于aaaak会增加到n循环因k n不满足而退出此时i和j仍为 0 和 1。返回min(i, j)而不是i或j。Math.min(i, j)能正确处理这种情况。算法结果与暴力枚举结果不一致1. 边界条件处理错误空串、单字符。2. 字符比较逻辑写反和。3. 取模运算错误。1. 首先测试空串和单字符a。2. 用一个小例子如cbaa单步调试观察i,j,k的变化。3. 检查(ik) % n是否正确模拟了循环。1. 在函数开头处理空串和单字符情况。2. 牢记当a b时说明从i开始的串更大应淘汰i。3. 确认使用% n而不是% (n*2)。在力扣题目中超时错误地写成了 O(n²) 的暴力算法或者最小表示法实现有误导致退化。检查你的算法是否包含了“跳跃”逻辑i i k 1。如果每次只i或j那就退化成 O(n²) 了。严格遵循模板中的跳跃逻辑。确保在字符不相等时是跳k1步而不是 1 步。处理数字字符串时结果不符合预期字典序比较是基于字符的 ASCII 码。2(50) 10的第一个字符1(49)。理解字典序的定义。数字字符串123和234的比较与数值大小无关是逐字符比较1vs2。如果希望按数值大小比较循环表示需要先将字符串转换为数字列表并自定义比较逻辑或者使用其他方法如 DP。8. 最佳实践与工程建议虽然最小表示法代码很短但在工程应用和竞赛中遵循一些最佳实践能让代码更健壮、更高效。封装成工具函数 如上面的代码所示将min_representation和get_min_representation_string封装成独立的函数。在解决具体问题时直接调用即可避免重复编写和出错。处理空串和单字符串 在函数开头添加边界检查。对于空串可以返回 0 或 -1根据约定。对于单字符串算法也能正确工作但显式处理可以使逻辑更清晰。空间复杂度优化 我们的实现是 O(1) 额外空间的因为我们使用了取模运算没有复制字符串。这是最优的。不要为了“方便”而先构造s s那样会使用 O(n) 的额外空间。与字符串哈希结合 在需要频繁比较两个字符串的循环同构关系或者需要对大量字符串的最小表示进行去重时可以先求出每个字符串的最小表示然后计算这个最小表示的哈希值如多项式滚动哈希。用哈希值进行比较或存入哈希集合效率极高。# 示例使用最小表示法进行字符串循环同构去重 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} (前三个是循环同构后三个是循环同构)理解算法局限性 最小表示法解决的是精确匹配问题。对于允许有容错如编辑距离的模糊匹配场景它不适用。它的核心是比较字典序。在力扣周赛中的策略识别题型 题目描述中出现“循环”、“旋转”、“是否可以通过旋转得到”等关键词并且数据范围较大n 可达 10^5应立刻想到最小表示法。模板化 将代码模板保存在本地比赛时快速复制粘贴稍作修改即可。测试用例 务必测试全相同字符、升序、降序等边界情况。扩展最大表示法 只需将代码中的比较符号反转即可。寻找字典序最大的循环同构串把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) 解法了。
如果你在力扣周赛里遇到一道字符串题题目要求你判断两个循环字符串是否相等或者找出一个字符串的最小字典序表示你会怎么做很多人的第一反应可能是把字符串复制一份拼接起来然后枚举所有可能的起点用substring截取并比较。这个思路直观但时间复杂度是 O(n²)当字符串长度达到 10⁵ 级别时必然会超时。这正是力扣周赛 511 中一道题目的核心难点。这道题考察的是一个在字符串算法竞赛中经典但在日常工程开发中鲜为人知的算法——最小表示法。它能在 O(n) 时间内为一个循环字符串找到其所有循环同构串中字典序最小的那个。听起来很神奇其实它的核心思想是“双指针贪心比较”代码极其简洁通常不超过 20 行。本文将彻底拆解这个算法。我们不只告诉你“最小表示法是什么”更重要的是讲清楚为什么需要它直接枚举法在力扣周赛里为什么行不通它是如何工作的双指针i和j是如何协作一步步排除无效起点最终锁定答案的怎么写代码我们会给出 Java、Python 等多种语言的模板并逐行注释。有哪些坑比如字符串所有字符都相同时的特殊情况如何处理除了周赛它还能用在哪字符串匹配、数据去重等实际场景。无论你是为了备战周赛还是想深入理解字符串算法的精妙之处这篇文章都将为你提供一份可直接“复制-粘贴-理解”的实战指南。1. 这篇文章真正要解决的问题在力扣周赛、牛客竞赛等编程比赛中字符串处理是高频考点。有一类问题可以抽象为“循环同构串”的判断或查找。什么是循环同构串对于一个字符串s将其首尾相接形成一个环从任意位置开始、沿顺时针方向取出长度为n的字符串都称为s的一个循环同构串。例如字符串abcd的循环同构串包括abcd,bcda,cdab,dabc。常见的题目形式给定两个字符串判断它们是否是循环同构的即是否可以通过循环移位变得相同。给定一个字符串找出其所有循环同构串中字典序最小的一个即“最小表示”。基于最小表示法进行字符串哈希用于快速比较或去重。暴力法的瓶颈最直观的解法是对于长度为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 码。例如abcabd因为第三个字符cd。2.2 算法核心思想双指针与贪心淘汰算法的目标是找到最小表示的起始下标ans。我们初始化两个指针i 0,j 1它们代表两个待比较的候选起点。再初始化一个偏移量k 0表示从i和j开始已经连续匹配了k个字符。算法的核心过程是一个while循环在i n j n k n的条件下进行比较字符s[(ik) % n]和s[(jk) % n]。如果它们相等 ()说明从i和j开始的前k1个字符都一样我们无法判断谁更优于是k继续比较下一个字符。如果s[(ik) % n]大于s[(jk) % n]这意味着从i开始的字符串在当前位置的字典序大于从j开始的。那么以i为起点以及i1, i2, ..., ik这些点为起点的字符串都不可能是最小表示。为什么因为我们已经找到了一个比它们更小的候选j并且在至少前k1个字符上j都不比i差实际上在第k位更小。因此我们可以安全地将i直接跳到i k 1。同时k重置为 0。同理如果s[(ik) % n]小于s[(jk) % n]则说明j及其后面一段不可能是最小表示将j跳到j k 1k重置为 0。这里有一个关键优化如果i和j在跳转后重合了我们让j以保证两个指针指向不同的起点进行比较。当k达到n时说明整个字符串都匹配上了此时任意一个指针指向的起点都是最小表示通常发生在字符串所有字符都相同时。循环结束后ans是i和j中的较小值。为什么是 O(n)每次比较 (s[ik]vss[jk])无论结果如何指针i或j都会至少向前移动一步通过i k1或j k1。而i和j都不会超过n因此总的比较次数是 O(n) 级别的。3. 环境准备与前置条件本算法是纯逻辑算法不依赖任何特定的库或框架。你只需要编程语言 任何支持字符串操作和基础循环的语言均可。本文将以Java和Python为例进行演示因为它们分别是力扣竞赛和日常开发中最常用的语言之一。一个可以运行代码的环境 力扣的在线判题系统、本地的 IDE如 IntelliJ IDEA, VS Code, PyCharm或简单的文本编辑器配合命令行均可。对字符串和数组的基本操作 了解如何访问字符串中的字符注意 Java 中用charAt()Python 中可直接索引。4. 核心流程拆解让我们将上一节的思想转化为清晰的步骤。输入 一个字符串s长度为n。输出 该字符串最小表示的起始下标ans。算法步骤初始化n s.length()i 0,j 1,k 0ans暂不需要最后取min(i, j)主循环 当i n j n k n时重复步骤 3-6。字符比较计算a s[(i k) % n]计算b s[(j k) % n]情况一字符相等(a b)说明当前比较的两个候选序列在前k1位都相同无法决出胜负。操作k继续比较下一位。情况二i序列更大(a b)说明从j开始的序列在当前位更小i及其后面连续k个起点都不可能是答案。操作i i k 1。如果i j则i避免指针重合。k 0重置匹配长度。情况三j序列更大(a b)说明从i开始的序列在当前位更小j及其后面连续k个起点都不可能是答案。操作j j k 1。如果i j则j。k 0。循环结束与结果返回循环终止条件之一是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 到 ik 都不可能为答案 i i k 1; if (i j) { i; // 保证 i 和 j 不同 } k 0; // 重置匹配长度 } else { // a b // s[j...] 的字典序大于 s[i...]j 到 jk 都不可能为答案 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) \); } }代码关键点解析s.charAt((i k) % n) 通过取模运算% n来模拟循环访问避免了实际构造双倍字符串ss的空间开销。if (i j) { i; } 这是关键细节。当指针跳转后重合必须让其中一个指针前进一位否则比较会陷入死循环自己和自己比永远相等。Math.min(i, j) 循环结束时i和j至少有一个是有效答案。取较小者是为了保证索引在[0, n)范围内在循环中i或j有可能因为k1而暂时等于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 实现的注意点逻辑与 Java 版完全一致。Python 中字符串索引s[i]是 O(1) 操作。构造最小表示字符串时s[idx:] s[:idx]的切片操作非常高效和直观。6. 运行结果与效果验证运行上述 Java 或 Python 的测试代码你会得到类似以下的输出测试字符串: cbaa 最小表示起始索引: 2 最小表示字符串: aacb 测试字符串: abca 最小表示起始索引: 0 最小表示字符串: abca 测试字符串: aaaa 最小表示起始索引: 0 最小表示字符串: aaaa 测试字符串: bcab 最小表示起始索引: 1 最小表示字符串: abbc如何验证结果的正确性手动枚举对于短字符串可以手动列出其所有循环同构串找出字典序最小的看是否与程序输出一致。例如cbaa0: cbaa1: baac2: aacb← 最小3: acba程序输出索引 2字符串aacb正确。使用暴力法对照写一个 O(n²) 的暴力算法对小规模数据n 1000进行随机测试与最小表示法的结果对比确保一致。在力扣上提交寻找相关的题目例如 LeetCode 796. 旋转字符串或者一些周赛题目用这个算法模板提交看是否能通过所有测试用例。复杂度验证你可以尝试用这个算法处理一个长度为 10⁶ 的随机字符串。O(n) 的算法会在毫秒级完成而 O(n²) 的暴力算法将完全无法运行。这是算法效率最直接的证明。7. 常见问题与排查思路在实现和使用最小表示法时你可能会遇到以下问题问题现象可能原因排查方式解决方案程序陷入死循环指针i和j在跳转后重合且没有处理。检查if (a b)和else分支中在更新i或j后是否添加了if (i j) { i; }或类似逻辑。确保在指针跳转后如果i j则让其中一个指针向前移动一位。结果索引不正确对于全相同字符的串循环结束时i或j可能等于n因为i i k 1且k可能接近n。在循环结束后打印i和j的值。对于aaaak会增加到n循环因k n不满足而退出此时i和j仍为 0 和 1。返回min(i, j)而不是i或j。Math.min(i, j)能正确处理这种情况。算法结果与暴力枚举结果不一致1. 边界条件处理错误空串、单字符。2. 字符比较逻辑写反和。3. 取模运算错误。1. 首先测试空串和单字符a。2. 用一个小例子如cbaa单步调试观察i,j,k的变化。3. 检查(ik) % n是否正确模拟了循环。1. 在函数开头处理空串和单字符情况。2. 牢记当a b时说明从i开始的串更大应淘汰i。3. 确认使用% n而不是% (n*2)。在力扣题目中超时错误地写成了 O(n²) 的暴力算法或者最小表示法实现有误导致退化。检查你的算法是否包含了“跳跃”逻辑i i k 1。如果每次只i或j那就退化成 O(n²) 了。严格遵循模板中的跳跃逻辑。确保在字符不相等时是跳k1步而不是 1 步。处理数字字符串时结果不符合预期字典序比较是基于字符的 ASCII 码。2(50) 10的第一个字符1(49)。理解字典序的定义。数字字符串123和234的比较与数值大小无关是逐字符比较1vs2。如果希望按数值大小比较循环表示需要先将字符串转换为数字列表并自定义比较逻辑或者使用其他方法如 DP。8. 最佳实践与工程建议虽然最小表示法代码很短但在工程应用和竞赛中遵循一些最佳实践能让代码更健壮、更高效。封装成工具函数 如上面的代码所示将min_representation和get_min_representation_string封装成独立的函数。在解决具体问题时直接调用即可避免重复编写和出错。处理空串和单字符串 在函数开头添加边界检查。对于空串可以返回 0 或 -1根据约定。对于单字符串算法也能正确工作但显式处理可以使逻辑更清晰。空间复杂度优化 我们的实现是 O(1) 额外空间的因为我们使用了取模运算没有复制字符串。这是最优的。不要为了“方便”而先构造s s那样会使用 O(n) 的额外空间。与字符串哈希结合 在需要频繁比较两个字符串的循环同构关系或者需要对大量字符串的最小表示进行去重时可以先求出每个字符串的最小表示然后计算这个最小表示的哈希值如多项式滚动哈希。用哈希值进行比较或存入哈希集合效率极高。# 示例使用最小表示法进行字符串循环同构去重 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} (前三个是循环同构后三个是循环同构)理解算法局限性 最小表示法解决的是精确匹配问题。对于允许有容错如编辑距离的模糊匹配场景它不适用。它的核心是比较字典序。在力扣周赛中的策略识别题型 题目描述中出现“循环”、“旋转”、“是否可以通过旋转得到”等关键词并且数据范围较大n 可达 10^5应立刻想到最小表示法。模板化 将代码模板保存在本地比赛时快速复制粘贴稍作修改即可。测试用例 务必测试全相同字符、升序、降序等边界情况。扩展最大表示法 只需将代码中的比较符号反转即可。寻找字典序最大的循环同构串把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) 解法了。
