今天的每日一题看起来很短短到题面都没写完。原题信息停在“然后执行下面两者之一”后边的两个分支没有给全。我把这道题的常见完整定义补上给定一个只包含小写英文字母的字符串 s长度为 n必须恰好执行一次操作——选择一个整数 k1 ≤ k ≤ n然后执行下面两者之一操作一反转前 k 个字符把这 k 个字符移动到字符串末尾操作二反转后 k 个字符把这 k 个字符移动到字符串开头。目标是求经过一次操作后字典序最小的字符串。整体用 Go 来实现。这道题初看简单但我在本地敲了快两个小时主要时间不是耗在算法思路上而是耗在候选串的比较上——因为候选串全是拼接出来的直接构造再排序很容易但规模一旦到十万级就必须解决“两个拼接串怎么快速比较字典序”的问题。1. 题目语义被截断我先补全两种操作的准确表达原题信息停在“然后执行下面两者之一”后面的内容丢失了。我按这类反转题最常见的定义把两种操作落到代码上先写出暴力版本的变换公式后面所有优化都基于这两个表达式。用 Go 的切片语义表达n : len(s) // 操作一反转前 k 个字符放到字符串末尾 t1 : s[k:] reverseString(s[:k]) // 操作二反转后 k 个字符放到字符串开头 // rev 是 s 的反转串rev[:k] 恰好等于 reverse(s[n-k:]) rev : reverseString(s) t2 : rev[:k] s[:n-k]这里有一个容易误解的点操作二写成reverse(s[n-k:]) s[:n-k]与rev[:k] s[:n-k]完全等价因为如果把原串整体反转得到 rev那么原串最后 k 个字符反转到开头后刚好就是 rev 的前 k 个字符。用 s cba 验证一下k1t1 ba c bact2 a cb acbk2t1 a bc abct2 ab c abck3t1 abc abct2 cba cba最小结果是 abc。再看两个边界行为后面会用到kn 时t1 是整串反转t2 是原串k1 时t1 是把首字符移到末尾t2 是把尾字符移到开头。如果题目描述里操作分支不是这个版本最终答案集合可能会有细微差别但本文的算法框架不变只需要替换候选生成公式即可。我建议在真正实现前先把题面里每一句话都确认清楚尤其是“两者之一”这种截断位置漏掉任何一个分支都会导致答案不对。2. “最小字符开头”直觉翻车暴力枚举才是安全起点我刚拿到题时第一反应很朴素字典序最小先找整个串里最小的字符然后想办法让这个最小字符出现在开头。对于 s cba最小字符是 a用操作二 k2 把后缀 ba 反转成 ab 放到开头得到 abc这个直觉确实成立。但换一个数据立刻翻车。看 s acbaa 已经在开头原串看起来已经很小了可实际枚举所有 k 的结果如下k操作一结果操作二结果1cbaaacba2bacaabac3abcaabca4abcaacba最小结果是 abac来自 k2 的操作二比原串 acba 还要小。原因不是把某个最小字符提到开头而是把后缀 ba 反转成 ab 作为前缀让整个串的前两个字符从 ac 变成了 ab。所以结论很明确必须老老实实枚举 k1..n 的两种操作不能只凭“找最小字符”的直觉下结论。暴力代码如下func brute(s string) string { n : len(s) rev : reverseString(s) // 初始候选kn 的操作一即整串反转 best : rev for k : 1; k n; k { // 操作一s[k:] reverse(s[:k]) cur : s[k:] reverseString(s[:k]) if cur best { best cur } // 操作二reverse(s[n-k:]) s[:n-k] cur rev[:k] s[:n-k] if cur best { best cur } } return best } func reverseString(s string) string { b : []byte(s) for i, j : 0, len(b)-1; i j; i, j i1, j-1 { b[i], b[j] b[j], b[i] } return string(b) }这个暴力版本的时间复杂度是 O(n^2)因为每次构造字符串都要 O(n) 的切片和拼接成本。n 在 2000 以内时很稳问题规模再大就跑不动了。更关键的是它给出了一个绝对正确的参照实现后面做优化时可以用它来对拍验证。3. 把拼接候选拆成 s 与 rev 上的两段区间要优化不能真的构造出 2n 个完整字符串。我先观察这些候选串的结构规律。定义 rev reverse(s)即原串的反转串。操作一t1 s[k:] reverse(s[:k])可以改写为t1 s[k:n] rev[n-k:n]第一段是原串的区间[k, n)第二段是反转串的区间[n-k, n)。操作二t2 reverse(s[n-k:]) s[:n-k]可以改写为t2 rev[0:k] s[0:n-k]第一段是反转串的区间[0, k)第二段是原串的区间[0, n-k)。所有候选串的长度都是 n并且每个候选都能表示成“s 上的一段 rev 上的一段”或者“rev 上的一段 s 上的一段”。接下来是整篇文章最关键的一步候选串的字符位置映射。对 t1用变量 L n-k 表示第一段长度位置 p L 时字符来自 s[kp]位置 p L 时字符来自 rev[p]。为什么第二段可以直接用rev[p]因为第二段在 rev 上的起始偏移是 n-k局部偏移为 p-L p-(n-k)整体索引是 (n-k) (p-(n-k)) p。这个巧合让 t1 的字符映射变得非常简洁。对 t2用 L k 表示第一段长度位置 p L 时字符来自 rev[p]位置 p L 时字符来自 s[p-k]。有了这个映射就能在 O(1) 时间内取出任意候选的任意位置字符也能在 O(1) 时间内求任意候选任意区间的哈希。这样就不需要真的构造完整字符串了。4. 哈希加二分实现 O(n log n) 的最小候选筛选现在进入核心实现。我的目标是枚举 2n 个候选同时维护当前最优候选每个候选与最优候选比较字典序的复杂度控制在 O(log n)。比较两个长度都为 n 的字符串字典序可以先用二分找到最长公共前缀 LCP然后比较 LCP 后的第一个字符。LCP 的判断用哈希完成。我选择 uint64 自然溢出的滚动哈希base 取 131。如果担心碰撞可以改成双模后面会说怎么改。先定义预处理数组var hs, hr, pow []uint64 func initHash(s, rev string) { n : len(s) hs make([]uint64, n1) hr make([]uint64, n1) pow make([]uint64, n1) pow[0] 1 for i : 0; i n; i { hs[i1] hs[i]*base uint64(s[i]) hr[i1] hr[i]*base uint64(rev[i]) pow[i1] pow[i] * base } } func getHash(h []uint64, l, r int) uint64 { // 返回 h[l:r] 的哈希值l 包含r 不包含 return h[r] - h[l]*pow[r-l] }候选用一个结构体表示不需要真正构造字符串type Cand struct { typ int // 1 表示操作一2 表示操作二 k int } func firstLen(c Cand) int { n : len(hs) - 1 if c.typ 1 { return n - c.k } return c.k }firstLen返回候选串第一段的长度。操作一第一段是s[k:n]长度 n-k操作二第一段是rev[0:k]长度 k。然后实现候选串任意区间的哈希。这里的区间拼接逻辑是整个实现的难点我写了详细注释// hashOf 返回候选串在 [l, r) 区间的哈希值 func hashOf(c Cand, l, r int) uint64 { n : len(hs) - 1 L : firstLen(c) if r L { // 整个区间都在第一段 if c.typ 1 { return getHash(hs, c.kl, c.kr) } return getHash(hr, l, r) } if l L { // 整个区间都在第二段 if c.typ 1 { // 操作一第二段是 rev[n-k:n]但映射到 rev 的索引恰好是 [l, r) return getHash(hr, l, r) } // 操作二第二段是 s[0:n-k] return getHash(hs, l-c.k, r-c.k) } // 跨两段第一段取部分第二段取部分拼接 var h1, h2 uint64 if c.typ 1 { h1 getHash(hs, c.kl, n) // s 上的剩余部分 h2 getHash(hr, L, r) // rev 上的第二段部分 } else { h1 getHash(hr, l, c.k) // rev 上的第一段部分 h2 getHash(hs, 0, r-c.k) // s 上的第二段部分 } return h1*pow[r-L] h2 }解释几个关键点操作一第二段的起始偏移是 n-k但前面推导过候选串位置 p 在第二段时对应 rev[p]所以区间[l, r)在第二段时直接取 rev 的[l, r)即可。操作二第二段是s[0:n-k]候选串位置 p 在第二段时对应s[p-k]所以区间[l, r)在第二段时取 s 的[l-k, r-k)。跨段时第一段取到所在字符串的结尾第二段从开头取到 r-L 的长度中间用 pow 拼接。接下来是取字符和二分 LCPvar sBytes, revBytes []byte func getChar(c Cand, pos int) byte { L : firstLen(c) if pos L { if c.typ 1 { return sBytes[c.kpos] } return revBytes[pos] } if c.typ 1 { return revBytes[pos] } return sBytes[pos-c.k] } func hashPrefix(c Cand, m int) uint64 { return hashOf(c, 0, m) } // lcpLen 返回两个候选串的最长公共前缀长度 func lcpLen(a, b Cand) int { n : len(sBytes) lo, hi : 0, n for lo hi { mid : (lo hi 1) 1 if hashPrefix(a, mid) hashPrefix(b, mid) { lo mid } else { hi mid - 1 } } return lo } func less(a, b Cand) bool { L : lcpLen(a, b) if L len(sBytes) { return false // 两个候选完全相同 } return getChar(a, L) getChar(b, L) }二分右边界直接取 n因为所有候选长度都是 nLCP 最大就是 n。这里用(lohi1)1的写法是为了避免死循环当 lo 和 hi 相邻时mid 取 hi。主流程就非常简单了func solve(s string) string { n : len(s) rev : reverseString(s) sBytes []byte(s) revBytes []byte(rev) initHash(s, rev) best : Cand{typ: 1, k: n} // 初始候选整串反转 for k : 1; k n; k { c1 : Cand{typ: 1, k: k} if less(c1, best) { best c1 } c2 : Cand{typ: 2, k: k} if less(c2, best) { best c2 } } return build(s, rev, best) } func build(s, rev string, c Cand) string { n : len(s) if c.typ 1 { return s[c.k:] rev[n-c.k:] } return rev[:c.k] s[:n-c.k] }整体复杂度初始化哈希数组O(n)枚举 2n 个候选O(n)每次 less 比较二分 O(log n)每次哈希判断 O(1)总时间复杂度 O(n log n)空间复杂度 O(n)。n 到 20 万级别都能轻松跑完。这里补充一个选型问题为什么不用后缀数组后缀数组确实可以做到 O(n log n) 甚至 O(n)但实现复杂度明显更高。哈希加二分是“够用且不容易写崩”的方案。缺点是需要处理哈希碰撞实际工程里如果数据是人为构造的单哈希有被卡的风险比赛场景建议上双哈希。5. 边界条件、哈希碰撞与对拍验证我在调试过程中踩了几个坑逐个说一说。第一个坑是 reverseString 对空串的处理。比如 kn 时操作一里s[:n]的反转是整串反转没有空串问题但s[k:]当 kn 时是空串空串的反转还是空串用 []byte 转换后做交换循环时要注意不能索引越界。我上面的实现里直接用了两指针交换len0 时循环不执行天然安全。第二个坑是哈希拼接时第二段起始索引的推导。操作一里rev[n-k:n]这一段在整体候选串中的第 L 个位置开始但映射到 rev 的索引时恰好是总位置 pos 本身。这个结论第一次看会觉得很跳跃我在写代码时差点写成了rev[n-k pos]那样就错了。验证方法很简单对候选串[L, r)区间取哈希应该等于getHash(hr, L, r)而不是从 n-k 重新偏移。第三个坑是二分边界。如果两个候选完全相同LCP 会等于 n这时 less 应该返回 false否则在最后比较字符时会越界。我在 main 函数里跑s aaaa时所有候选都相同这行处理必须提前 return。第四个坑是单哈希的碰撞问题。uint64 自然溢出在很多算法题里都能过但理论上有碰撞可能。如果追求更稳可以改成双哈希type Pair struct { h1, h2 uint64 }两个 base 分别取 131 和 13331模数用 2^64 自然溢出即可。比较时先比 h1再比 h2。代码改动很小但能大幅降低碰撞概率。我写完后专门做了一轮对拍生成 1000 组随机小写字符串长度从 1 到 8同时跑暴力 O(n^2) 版本和哈希二分版本结果全部一致。对拍是这类“优化版”算法题最可靠的验证手段。如果你在面试或竞赛中写这种带哈希的代码务必先写一个暴力版本再用随机数据验证否则很难发现自己推导中的边界错误。第五个坑是性能。暴力版本在 n10000 时已经很吃力而哈希二分版本在 n200000 时依然很快。我随手写了个测试s : strings.Repeat(a, 200000) // 优化版本运行毫秒级但注意如果字符串全相等所有候选都相同二分比较时会立刻返回 LCPn不会退化到最坏情况。最坏情况反而出现在字符串结构“有长公共前缀但最后不同”的场景此时二分会跑满 log(n) 层不过每一次哈希比较都是 O(1)整体依然稳定。6. 追加约束时的处理思路和最终体会有些面试官会在原题基础上追加一句结果不能等于原字符串。这种情况需要特殊处理。在哈希版本里判断候选是否等于原串非常方便候选长度固定为 n只要hashPrefix(c, n)等于getHash(hs, 0, n)就说明候选与原串相同。枚举时跳过这些候选即可。例如origHash : getHash(hs, 0, n) for k : 1; k n; k { c1 : Cand{typ: 1, k: k} if hashPrefix(c1, n) ! origHash less(c1, best) { best c1 } c2 : Cand{typ: 2, k: k} if hashPrefix(c2, n) ! origHash less(c2, best) { best c2 } }极端情况下如果所有候选都等于原串比如s aaaa那这个问题在原题约束下依然有解只是答案就是原串如果题目强行要求结果不同就无解。还有另一种常见变体限制 k 只能取 1 到 n-1即不允许把整串反转。去掉 kn 的候选即可代码只在枚举范围上改一个边界。最后再说一点我对这道题的整体感受。它真正难的其实不是哈希和二分而是把候选串的结构看清楚。两种操作看起来像是两个完全不同的变换但本质上都只是提供了 2n 个等长候选串每个候选又都能拆成 s 和 rev 上的两段区间。一旦这个结构被拆开哈希拼接和二分比较就是自然而然的事情。我之前见过不少“拼接候选排序”的题比如按某种规则生成回文串、循环移位、前后缀组合等处理方式几乎都是同一个套路把候选串表示为两个数组上的区间然后用哈希或后缀数组加速比较。这道题算是这类问题里比较典型的一个代表值得记下来。