2026-10-22：字符串变换后的最少分组数。用go语言，给定一个字符串集合。对其中任意一个字符串，先按字符所在位置分成两串：位置编号为 1、3、5……的字符按原顺序组成一串，位置编号为 2、4、6……的字符按原顺序组成另一串。然后允许分别把这两串字符做任意次循环平移，平移次数可以是零；最后再按原来的位置交错放回，得到一个新字符串。
如果两个字符串能够通过上述方式变成同一个字符串，就认为它们属于同一种形态。现在要把所有给定字符串分成若干组，要求每个字符串只出现在一个组里，并且同一组内任意两个字符串都具有这种相同形态。问最少需要分成多少组。换句话说，就是统计这些字符串一共包含多少种不同的上述形态；长度不同的字符串不可能归为同一种形态。
1 <= words.length <= 100000
1 <= words[i].length <= 500000
所有 words[i].length 之和不超过 500000。
words[i] 仅由小写英文字母组成。
输入： words = ["ntgwz","zwntg"]。
输出： 1。
解释：
对于 "ntgwz"，偶数下标字符组成的子序列为 "ngz"，奇数下标字符组成的子序列为 "tw"。
将 "ngz" 向右循环移动 1 位，得到 "zng"；将 "tw" 向右循环移动 1 位，得到 "wt"。
重新构造字符串后，得到 "zwntg"。
因此，这两个字符串等价，可以划分到同一组中。
题目来自力扣3999。
大体步骤如下：
一、把字符串拆成两个子序列
对每个字符串，按照字符下标的奇偶性拆成两个部分：
1. 收集偶数下标位置的字符。代码中下标从 0 开始，所以收集的是第 0、2、4……个字符；对应题目中位置编号为 1、3、5……的字符。
2. 收集奇数下标位置的字符。代码中收集的是第 1、3、5……个字符；对应题目中位置编号为 2、4、6……的字符。
这两个子序列都保持字符在原字符串中的相对顺序。拆分后，原字符串长度等于两个子序列长度之和。对于长度为 1 的字符串，第二个子序列为空串，这是允许的。
二、对两个子序列分别求“字典序最小的循环同构串”
题目允许分别对偶数位子序列和奇数位子序列做任意次向右循环移动。一个序列向右循环移动若干次，本质上就是把这个序列看成一个环，从某个位置开始重新读一圈。所有可能的移动结果，就是这个序列的所有循环旋转。
为了比较两个序列是否可以通过循环移动互相转化，不需要枚举所有移动次数，而是为每个序列选一个唯一的代表：在所有循环旋转中，字典序最小的那个串。这个代表称为“最小循环表示”或“最小表示”。两个序列循环同构，当且仅当它们的最小循环表示完全相同。
求一个长度为 m 的序列的最小表示时，代码使用双指针排除法：
1. 先把序列看成“原序列接上自身”得到的长度为 2m 的串，这样从任意起点读取连续 m 个字符，就对应原序列的一个循环旋转。
2. 维护两个候选起点，初始分别指向第 0 个位置和第 1 个位置。目标是在这些起点中找到从哪个起点开始读出的长度为 m 的串字典序最小。
3. 从两个候选起点开始逐字符比较。假设比较到第 k 个字符时第一次出现不同：
• 如果前一个候选起点对应的字符更小，那么从后一个候选起点到它后面连续若干位置开始的旋转，都不可能是最小表示，因为它们在第一次不同处已经输给了前一个候选对应的旋转。于是把后一个候选起点直接跳过这一整段，移到第一个不同位置之后。
• 如果后一个候选起点对应的字符更小，说明后一个候选更优。此时前一个候选起点以及它后面一段起点都不可能是答案，于是把前一个候选起点更新为后一个候选起点，同时把后一个候选起点跳到至少旧后一个候选起点的下一个位置，并且至少跳过刚刚比较过的那一段，取二者中较大的位置。
4. 如果在比较过程中连续比较了 m 个字符都没有不同，说明两个候选起点读出的循环串完全相同，或者序列具有周期性。此时当前保存的较优候选起点已经可以作为最小表示的起点，停止比较。
5. 循环直到第二个候选起点到达原序列长度 m。最终第一个候选起点指向的位置，就是字典序最小循环旋转的起点；从该位置连续取 m 个字符，就是该序列的最小表示。
这个双指针过程看似有两层循环，但每一轮比较后都会排除掉一段不可能成为最小起点的位置，累计排除次数与序列长度同阶，因此求一个长度为 m 的序列的最小表示是线性时间。
三、把两个最小表示拼接成规范签名
对当前字符串的偶数位子序列求出最小表示，对奇数位子序列也求出最小表示。然后把“偶数位子序列的最小表示”放在前面，“奇数位子序列的最小表示”放在后面，拼接成一个新的字符串，作为当前原字符串的规范签名。
这里顺序必须固定，不能交换，也不能把两个最小表示排序。原因是偶数位和奇数位在变换中角色不同，拼接顺序保留了这种角色信息。同时，拼接后的总长度等于原字符串长度，所以长度不同的字符串天然会得到不同长度的签名，不会被误判为同一类。
四、用哈希集合统计不同签名
遍历所有给定字符串，对每个字符串都生成上述规范签名，然后把签名放入一个哈希集合中。哈希集合会自动去重：同一个签名无论出现多少次，只保留一个。遍历结束后，集合中元素的数量就是不同等价类的数量。
为什么集合大小就是最少分组数？
1. 如果两个字符串等价，那么它们的偶数位子序列循环同构，奇数位子序列也循环同构。循环同构的序列具有相同的最小表示，因此两个字符串生成的签名完全相同，会落在同一个集合元素中。
2. 反过来，如果两个字符串生成的签名相同，说明偶数位子序列的最小表示相同，奇数位子序列的最小表示也相同，因此两个子序列分别循环同构。于是可以分别对两个子序列做适当的循环移动，使两个字符串变成同一个字符串，所以它们等价。
3. 等价关系具有传递性，每个字符串只对应一个签名，所以每个字符串恰好属于一个等价类。每个等价类至少需要一组，而把一个等价类整体放成一组又一定满足组内任意两个等价，因此最少分组数正好等于等价类数量，也就是哈希集合的大小。
对于示例中的两个字符串，它们虽然表面不同，但按奇偶下标拆分后，两个子序列分别属于相同的循环同构类，因此得到相同的规范签名，集合大小为 1，输出 1。
五、复杂度分析
设所有输入字符串的长度总和为 N，即 N 等于所有 words[i].length 之和；设字符串个数为 M。
时间复杂度：
1. 对每个字符串按奇偶下标拆分，耗时与该字符串长度成正比。所有字符串合计 O(N)。
2. 对每个字符串的两个子序列分别求最小表示。两个子序列长度之和等于原字符串长度，而最小表示算法是线性的，所以每个字符串耗时 O(其长度)，所有字符串合计 O(N)。
3. 把两个最小表示拼接成签名，耗时 O(原字符串长度)。所有字符串合计 O(N)。
4. 把签名插入哈希集合。按通常哈希表的期望分析，计算字符串哈希和插入的期望代价与签名长度成正比，所有签名总长度不超过 N，因此总期望 O(N)。如果讨论哈希冲突的最坏理论情况，可能退化，但按常规算法分析使用期望 O(N)。
所以总时间复杂度为期望 O(N)，其中 N 是所有字符串长度之和。题目给出 N 不超过 500000，因此该复杂度足够。
额外空间复杂度：
1. 哈希集合需要保存所有不同的规范签名。每个签名长度等于对应原字符串长度，去重后保存的签名总字符数不会超过所有输入字符串总长度 N，因此集合占用 O(N)。
2. 处理单个字符串时，需要临时保存拆出的两个子序列、双指针求最小表示时的临时串以及拼接签名等，单个字符串的临时空间与其长度成正比。所有字符串依次处理，临时空间可以复用，峰值不会超过 O(N)。
3. 因此除输入字符串本身外，总额外空间复杂度为 O(N)。
package main
import (
"fmt"
)
// 返回 s 的字典序最小的循环同构串
// 时间复杂度 O(|s|)，证明见代码末尾的注释
func smallestRepresentation(s []byte) []byte {
n := len(s)
s = append(s, s...)
i := 0// 始终指向当前最小子串的首字母下标
j := 1// 指向需要和 i 比较的子串的首字母下标
for j < n {
// 暴力比较：是 i 开头的字典序小，还是 j 开头的字典序小？
k := 0
for k < n && s[i+k] == s[j+k] {
k++
}
if k >= n {
// s 是个周期字符串，周期为 j-i
// j+d 开头的子串等于 i+d 开头的子串，而这些子串我们之前已经排除了，继续遍历不会找到更小的
break
}
if s[i+k] < s[j+k] { // 注：如果求字典序最大，改成 >
// 比如从 i 开始是 "aaab"，从 j 开始是 "aaac"
// 从 i 开始比从 j 开始更小（排除 j）
// 此外：
// 从 i+1 开始比从 j+1 开始更小，所以从 j+1 开始不可能是答案，排除
// 从 i+2 开始比从 j+2 开始更小，所以从 j+2 开始不可能是答案，排除
// ……
// 从 i+k 开始比从 j+k 开始更小，所以从 j+k 开始不可能是答案，排除
// 所以下一个「可能是答案」的开始位置是 j+k+1
j += k + 1
} else {
// 从 j 开始比从 i 开始更小，更新 i=j（也意味着我们排除了 i）
// 此外：
// 从 j+1 开始比从 i+1 开始更小，所以从 i+1 开始不可能是答案，排除
// 从 j+2 开始比从 i+2 开始更小，所以从 i+2 开始不可能是答案，排除
// ……
// 从 j+k 开始比从 i+k 开始更小，所以从 i+k 开始不可能是答案，排除
// 所以把 j 跳到 i+k+1，不过这可能比 j+1 小，所以与 j+1 取 max
// 综上所述，下一个「可能是答案」的开始位置是 max(j+1, i+k+1)
i, j = j, max(j, i+k)+1
}
// 每次要么排除 k+1 个与 i 相关的位置（这样的位置至多 n 个），要么排除 k+1 个与 j 相关的位置（这样的位置至多 n 个）
// 所以上面关于 k 的循环，∑k <= 2n，所以二重循环的总循环次数是 O(n) 的
}
return s[i : i+n]
}
func minimumGroups(words []string) (ans int) {
set := map[string]struct{}{}
for _, word := range words {
// 按照下标的奇偶性分组
groups := [2][]byte{}
for i, ch := range word {
groups[i%2] = append(groups[i%2], byte(ch))
}
// 分别计算偶数组和奇数组的最小表示
s := smallestRepresentation(groups[0])
t := smallestRepresentation(groups[1])
set[string(append(s, t...))] = struct{}{}
}
returnlen(set)
}func main() {
words := []string{"ntgwz", "zwntg"}
result := minimumGroups(words)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
def smallest_representation(s: str) -> str:
"""
返回字符串 s 的字典序最小的循环同构串。
时间复杂度 O(|s|)。
"""
n = len(s)
if n == 0:
return""
ss = s + s # 相当于 Go 里的 s = append(s, s...)
i = 0 # 始终指向当前最小子串的首字母下标
j = 1 # 指向需要和 i 比较的子串的首字母下标
while j < n:
k = 0
# 暴力比较：以 i 开头和以 j 开头的子串哪个字典序更小
while k < n and ss[i + k] == ss[j + k]:
k += 1
if k >= n:
# s 是周期字符串，周期为 j-i
# 继续遍历不会找到更小的
break
if ss[i + k] < ss[j + k]:
# 从 i 开始比从 j 开始更小，排除 j 到 j+k 这些起点
j += k + 1
else:
# 从 j 开始比从 i 开始更小，更新 i=j
# 并排除 i 到 i+k 这些起点
i, j = j, max(j, i + k) + 1
return ss[i:i + n]
def minimum_groups(words) -> int:
seen = set()
for word in words:
# 按照下标的奇偶性分组
groups = ["", ""]
for idx, ch in enumerate(word):
groups[idx % 2] += ch
# 分别计算偶数组和奇数组的最小表示
s = smallest_representation(groups[0])
t = smallest_representation(groups[1])
# 用「偶数组最小表示 + 奇数组最小表示」作为等价类标识
seen.add(s + t)
returnlen(seen)
def main():
words = ["ntgwz", "zwntg"]
result = minimum_groups(words)
print(result)if __name__ == "__main__":
main()
C++完整代码如下：
using namespace std;
// 返回 s 的字典序最小的循环同构串
// 时间复杂度 O(|s|)
string smallestRepresentation(conststring& s) {
int n = (int)s.size();
if (n == 0) return"";
string ss = s + s; // 相当于 Go 里的 s = append(s, s...)
int i = 0; // 始终指向当前最小子串的首字母下标
int j = 1; // 指向需要和 i 比较的子串的首字母下标
while (j < n) {
// 暴力比较：是 i 开头的字典序小，还是 j 开头的字典序小？
int k = 0;
while (k < n && ss[i + k] == ss[j + k]) {
++k;
}
if (k >= n) {
// s 是个周期字符串，周期为 j-i
// j+d 开头的子串等于 i+d 开头的子串，而这些子串我们之前已经排除了
// 继续遍历不会找到更小的
break;
}
if (ss[i + k] < ss[j + k]) { // 注：如果求字典序最大，改成 >
// 比如从 i 开始是 "aaab"，从 j 开始是 "aaac"
// 从 i 开始比从 j 开始更小（排除 j）
// 此外：
// 从 i+1 开始比从 j+1 开始更小，所以从 j+1 开始不可能是答案，排除
// 从 i+2 开始比从 j+2 开始更小，所以从 j+2 开始不可能是答案，排除
// ……
// 从 i+k 开始比从 j+k 开始更小，所以从 j+k 开始不可能是答案，排除
// 所以下一个「可能是答案」的开始位置是 j+k+1
j += k + 1;
} else {
// 从 j 开始比从 i 开始更小，更新 i=j（也意味着我们排除了 i）
// 此外：
// 从 j+1 开始比从 i+1 开始更小，所以从 i+1 开始不可能是答案，排除
// 从 j+2 开始比从 i+2 开始更小，所以从 i+2 开始不可能是答案，排除
// ……
// 从 j+k 开始比从 i+k 开始更小，所以从 i+k 开始不可能是答案，排除
// 所以把 j 跳到 i+k+1，不过这可能比 j+1 小，所以与 j+1 取 max
// 综上所述，下一个「可能是答案」的开始位置是 max(j+1, i+k+1)
int newJ = max(j, i + k) + 1;
i = j;
j = newJ;
}
// 每次要么排除 k+1 个与 i 相关的位置（这样的位置至多 n 个），要么排除 k+1 个与 j 相关的位置（这样的位置至多 n 个）
// 所以上面关于 k 的循环，∑k <= 2n，所以二重循环的总循环次数是 O(n) 的
}
return ss.substr(i, n);
}
int minimumGroups(const vector& words) {
set seen;
for (conststring& word : words) {
// 按照下标的奇偶性分组
string groups[2];
for (int idx = 0; idx < (int)word.size(); ++idx) {
groups[idx % 2].push_back(word[idx]);
}
// 分别计算偶数组和奇数组的最小表示
string s = smallestRepresentation(groups[0]);
string t = smallestRepresentation(groups[1]);
// 用「偶数组最小表示 + 奇数组最小表示」作为等价类标识
seen.insert(s + t);
}
return (int)seen.size();
}int main() {
vector words = {"ntgwz", "zwntg"};
int result = minimumGroups(words);
cout << result << endl;
return0;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
热门跟贴