这次我们来看一个在力扣周赛 511 中出现的算法问题它背后涉及到一个经典且高效的字符串处理算法——最小表示法。对于参加算法竞赛或准备技术面试的开发者来说掌握这个算法不仅能帮你快速解决特定类型的字符串循环同构问题更能优化你的解题思路提升代码效率。最小表示法的核心目标是找到一个循环字符串的所有表示形式中字典序最小的那个。听起来有点抽象简单来说给定一个字符串比如 “bcdea”你可以把它想象成一个环从任意位置切开都能得到一个线性字符串。最小表示法就是找出所有这些线性字符串里排在最前面的那个按字母顺序比较。在力扣周赛 511 中这类问题往往以“判断两个字符串是否循环同构”或“找出循环字符串的最小表示”等形式出现直接考察你是否能高效实现该算法。本文将带你彻底搞懂最小表示法。我们会先快速了解它的核心能力和应用场景然后深入其 O(n) 时间复杂度的双指针算法原理接着通过力扣周赛 511 的典型例题进行实战演练最后给出完整的代码实现、复杂度分析以及常见问题排查方法。无论你是为了备战周赛还是想巩固字符串算法这篇文章都能提供直接的、可落地的帮助。1. 核心能力速览在深入细节前我们先通过一个表格快速把握最小表示法的关键信息能力项说明算法类型字符串算法用于处理循环同构问题核心功能寻找一个循环字符串的字典序最小或最大的表示形式时间复杂度O(n)其中 n 为字符串长度空间复杂度O(1) (仅使用几个指针变量)输入要求一个字符串或可以视为循环序列的数组输出结果最小表示形式在原串中的起始下标或直接构造出的最小表示字符串典型应用场景力扣周赛字符串难题、判断字符串循环同构、字符串匹配的预处理前置知识双指针技巧、字符串字典序比较2. 适用场景与使用边界最小表示法并非通用字符串算法它在特定场景下能发挥巨大威力。它最适合谁算法竞赛选手尤其是参加力扣周赛、Codeforces、AtCoder 的选手遇到“循环同构”、“最小循环表示”类题目时这是标准解法。面试备考者国内大厂面试中字符串处理是高频考点。掌握最小表示法能让你在面对“判断两个字符串是否通过旋转得到”这类问题时给出最优解。需要处理循环数据的研究者例如在生物信息学中分析环形DNA序列或在数据处理中分析周期性信号。它能解决什么问题判断循环同构给定两个字符串s和t判断是否可以通过将s循环旋转若干位得到t。最朴素的方法是拼接ss然后看t是否为其子串时间复杂度 O(n²)。而使用最小表示法可以先将s和t都转化为其最小表示然后直接比较这两个最小表示是否相等时间复杂度降至 O(n)。寻找最小表示直接求出一个字符串的最小字典序循环表示。这是算法的直接应用。解决依赖循环表示的衍生问题许多题目需要你先获得字符串的最小表示然后在此基础上进行其他计算。它的边界在哪里不适用于非循环问题如果问题本质与字符串的循环移位无关则不需要此算法。通常用于单次计算算法本身计算一个字符串的最小表示。如果需要频繁对同一个字符串的不同子串求最小表示可能需要结合其他数据结构。字典序定义算法严格依赖于字符的字典序通常是ASCII或Unicode码点顺序。如果排序规则自定义需要修改比较逻辑。3. 算法原理与双指针实现最小表示法的核心是双指针i, j和增量比较。它能在 O(n) 时间内完成任务避免了 O(n²) 的暴力枚举。3.1 算法思想假设字符串长度为n。我们复制一份原字符串接到后面得到长度为2n的字符串S这样任何循环起点k开始的n个字符就是S[k:kn]。 算法维护两个候选起点i和j以及一个当前匹配长度k。初始化i 0,j 1,k 0。在i n且j n的条件下循环比较S[ik]和S[jk]。如果相等k继续比较下一个字符。如果S[ik] S[jk]说明从i开始的表示在当前位置比从j开始的表示字典序大。那么对于任意i到ik之间的起点p都存在一个对应的j到jk之间的起点q使得表示更优。因此我们可以直接将i跳到ik1。同时如果跳完后i j需要让i以保证两个起点不同。如果S[ik] S[jk]同理将j跳到jk1。同样处理i j的情况。每次发生字符不相等后将k重置为 0。最终最小表示的起点是min(i, j)。3.2 算法正确性简要说明该算法可以理解为在2n的扩展串上i和j是两个“赛跑”的指针。通过比较S[ik]和S[jk]我们能确定哪一段连续的候选起点是“失败”的从而一次性跳过它们ik1。这确保了每个位置最多被比较常数次总时间复杂度为 O(n)。4. 环境准备与代码实现理解原理后我们来实现它。你不需要特殊的库或环境任何支持标准字符串操作的语言都可以。4.1 通用函数模板Python以下是最小表示法的标准实现返回最小表示在原串中的起始索引。def minimum_representation(s: str) - int: 返回字符串 s 的最小表示法的起始下标。 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: # a b j j k 1 # 如果指针重合让其中一个加1 if i j: j 1 k 0 # 重置匹配长度 # 返回较小的有效起点 return min(i, j) # 辅助函数获取最小表示的字符串 def get_min_representation(s: str) - str: idx minimum_representation(s) n len(s) return s[idx:] s[:idx]4.2 使用扩展字符串的实现更易理解另一种常见写法是显式构造一个s s的扩展字符串避免取模运算。def minimum_representation_extended(s: str) - int: n len(s) if n 0: return 0 extended_s s s i, j, k 0, 1, 0 while i n and j n and k n: a extended_s[i k] b extended_s[j k] 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.3 力扣周赛 511 例题实战假设周赛 511 中有一道题如下题目为模拟用于演示题目给你一个字符串s你可以将它循环旋转任意次。请返回你能得到的字典序最小的字符串。输入输出示例输入s “bcdea” 输出”abcde” 解释原串 “bcdea” 循环旋转一位得到 “cdeab”旋转两位得到 “deabc”旋转三位得到 “eabcd”旋转四位得到 “abcde”。其中 “abcde” 字典序最小。解题代码 直接使用我们上面实现的函数即可。class Solution: def minRotationString(self, s: str) - str: def minRep(s: str) - int: 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 else: if a b: i k 1 else: j k 1 if i j: j 1 k 0 return min(i, j) idx minRep(s) return s[idx:] s[:idx] # 测试 sol Solution() print(sol.minRotationString(bcdea)) # 输出: abcde print(sol.minRotationString(aaaa)) # 输出: aaaa print(sol.minRotationString(cba)) # 输出: acb5. 功能测试与效果验证实现算法后必须进行系统测试以确保正确性。我们将从简单到复杂设计测试用例。5.1 基础功能测试测试目的验证算法对典型输入能否返回正确的最小表示起始索引和字符串。def test_basic(): test_cases [ (bcdea, 4, abcde), # 常规情况 (aaaa, 0, aaaa), # 全相同字符 (abca, 3, aabc), # 有重复字符 (cba, 2, acb), # 最小表示在尾部 (a, 0, a), # 单字符 (, 0, ), # 空字符串 ] for s, expected_idx, expected_str in test_cases: idx minimum_representation(s) min_str get_min_representation(s) assert idx expected_idx, fFailed for {s}: got idx {idx}, expected {expected_idx} assert min_str expected_str, fFailed for {s}: got str {min_str}, expected {expected_str} print(f✓ {s} - idx:{idx}, str:{min_str}) print(所有基础测试通过) test_basic()5.2 性能与复杂度验证测试目的验证算法的时间复杂度是否为 O(n)以及处理长字符串时的实际表现。import time import random import string def test_performance(): # 生成长度递增的随机字符串 for length in [1000, 10000, 50000, 100000]: # 生成随机字符串 s .join(random.choices(string.ascii_lowercase, klength)) start_time time.time() idx minimum_representation(s) elapsed time.time() - start_time # 简单验证结果正确性通过与朴素算法比较仅在小长度时进行 if length 1000: # 朴素法找最小表示用于验证 naive_min min((s[i:] s[:i]) for i in range(len(s))) our_min s[idx:] s[:idx] assert naive_min our_min, f结果不一致length{length} print(f长度 {length:6d} - 耗时: {elapsed:.6f} 秒 - 起点索引: {idx}) # 经验上O(n)算法处理10万长度应在零点几秒内完成 test_performance()预期结果与判断所有基础测试应全部通过无断言错误。性能测试中运行时间应大致随字符串长度线性增长。对于10万长度的字符串在普通个人计算机上运行时间通常远小于1秒。如果时间远超此范围例如数秒可能需要检查实现是否有误导致退化。5.3 边界与压力测试测试目的验证算法在极端情况下的稳定性。全相同字符长串”a” * 100000。算法应快速返回索引0。递增序列”abcdefghijklmnopqrstuvwxyz” * 1000。最小表示就是它本身算法应在比较早期就确定结果。字典序递减序列”zyxwvutsrqponmlkjihgfedcba”。最小表示在最后一位旋转一次算法需要遍历较多次比较。6. 在力扣周赛中的应用模式在周赛中最小表示法很少直接作为题目要求实现而是作为解决更大问题的关键子步骤。以下是两种常见应用模式6.1 模式一判断循环同构问题特征题目要求判断两个字符串是否可以通过循环旋转相互得到。解题模板如果s和t长度不等直接返回False。分别求出s和t的最小表示。比较两个最小表示是否相等。def is_cyclic_isomorphic(s: str, t: str) - bool: if len(s) ! len(t): return False min_rep_s get_min_representation(s) min_rep_t get_min_representation(t) return min_rep_s min_rep_t6.2 模式二基于最小表示进行哈希或分组问题特征给出一组字符串需要将循环同构的字符串分到同一组。解题模板遍历每个字符串。计算其最小表示。使用最小表示作为键将原字符串存入字典哈希表中对应的列表。from collections import defaultdict def group_cyclic_strings(strs: List[str]) - List[List[str]]: groups defaultdict(list) for original_str in strs: key get_min_representation(original_str) # 最小表示作为键 groups[key].append(original_str) return list(groups.values())这种方法的时间复杂度是 O(N * L)其中 N 是字符串个数L 是字符串平均长度。比两两比较的 O(N² * L) 高效得多。7. 常见问题与排查方法在实现和使用最小表示法时你可能会遇到以下问题问题现象可能原因排查方式解决方案结果不正确返回的索引不对1. 指针跳转逻辑错误。2. 处理i j的情况有误。3. 取模运算或扩展字符串索引越界。1. 使用”bcdea”(应得4)、”abca”(应得3) 等简单用例调试。2. 单步跟踪i,j,k的变化。3. 检查循环条件是否包含k n。1. 严格对照本文 4.1 节的代码实现。2. 确保当a b时更新i反之更新j。3. 确保跳转后若i j执行j 1。算法陷入死循环循环条件不完整或指针更新后未正确推进。1. 检查while循环条件是否为i n and j n and k n。2. 在指针更新后打印i, j, k观察是否停滞。1. 确保三个条件缺一不可。2. 确认在字符不等时k被重置为0。处理空字符串时出错函数未对空字符串进行特判。输入空字符串””测试。在函数开始处添加判断if n 0: return 0。性能表现不佳对于长串很慢实现可能退化为 O(n²)例如在每次不匹配时只将指针移动一位。使用性能测试函数对比不同长度字符串的运行时间增长曲线。检查是否实现了“跳跃”优化即i i k 1而不是i i 1。这是保证 O(n) 的关键。需要求最大表示法题目要求字典序最大的循环表示。确认题目要求。只需修改比较逻辑将if a b:和else:中的指针更新规则对调。即当a b时更新i当a b时更新j。8. 最佳实践与使用建议为了在竞赛或工程中可靠地使用最小表示法遵循以下实践能让你少走弯路封装成可靠函数将算法实现为一个经过充分测试的函数如minimum_representation并放在你的代码模板中。比赛时直接复制使用避免现场调试。始终进行简单测试即使是从模板粘贴的代码在解题前也用一两个简单例子如”bcdea”快速验证一下函数的输出是否正确。理解而非死记虽然可以背模板但理解双指针为何能跳跃以及为何是 O(n) 复杂度有助于你在遇到变种题时灵活调整。注意字符串编码算法比较的是字符的底层编码如 ASCII。如果字符串包含 Unicode 字符且题目自定义了排序规则则需要修改比较部分a b的逻辑。空间与时间权衡使用“取模”版本节省了构造扩展字符串O(n)的空间但可能略微增加计算开销。使用“扩展字符串”版本更直观且访问连续内存可能更快。在力扣周赛等环境中通常n不会极大两种方式均可。结合其他算法最小表示法常作为字符串处理流水线的一环。例如先求出最小表示再对其进行哈希用于快速比较或分组。9. 总结与下一步最小表示法是一个精妙且高效的工具专门用于解决字符串循环同构问题。它的 O(n) 时间复杂度使其在力扣周赛等对性能要求高的场景下极具优势。通过本文你应该已经掌握了它的原理、标准实现、测试方法以及应用模式。要真正掌握它下一步你可以在力扣上搜索相关题目尝试搜索 “circular string”、“rotation” 等关键词寻找可以使用最小表示法的题目进行练习。尝试变种问题例如求最大表示法或者处理数字数组而非字符串的最小表示。分析更复杂的题目有些题目可能不会直接要求求最小表示但当你发现需要比较或分类循环序列时它就是潜在的解决方案。建议将本文的核心实现代码保存到你的算法工具箱中。当下次周赛再遇到“循环”、“旋转”、“最小字典序”这些关键词时你能立刻想起这个有力的武器并快速将其应用于解题。