2026-10-22字符串变换后的最少分组数。用go语言给定一个字符串集合。对其中任意一个字符串先按字符所在位置分成两串位置编号为 1、3、5……的字符按原顺序组成一串位置编号为 2、4、6……的字符按原顺序组成另一串。然后允许分别把这两串字符做任意次循环平移平移次数可以是零最后再按原来的位置交错放回得到一个新字符串。如果两个字符串能够通过上述方式变成同一个字符串就认为它们属于同一种形态。现在要把所有给定字符串分成若干组要求每个字符串只出现在一个组里并且同一组内任意两个字符串都具有这种相同形态。问最少需要分成多少组。换句话说就是统计这些字符串一共包含多少种不同的上述形态长度不同的字符串不可能归为同一种形态。1 words.length 1000001 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。大体步骤如下一、把字符串拆成两个子序列对每个字符串按照字符下标的奇偶性拆成两个部分收集偶数下标位置的字符。代码中下标从 0 开始所以收集的是第 0、2、4……个字符对应题目中位置编号为 1、3、5……的字符。收集奇数下标位置的字符。代码中收集的是第 1、3、5……个字符对应题目中位置编号为 2、4、6……的字符。这两个子序列都保持字符在原字符串中的相对顺序。拆分后原字符串长度等于两个子序列长度之和。对于长度为 1 的字符串第二个子序列为空串这是允许的。二、对两个子序列分别求“字典序最小的循环同构串”题目允许分别对偶数位子序列和奇数位子序列做任意次向右循环移动。一个序列向右循环移动若干次本质上就是把这个序列看成一个环从某个位置开始重新读一圈。所有可能的移动结果就是这个序列的所有循环旋转。为了比较两个序列是否可以通过循环移动互相转化不需要枚举所有移动次数而是为每个序列选一个唯一的代表在所有循环旋转中字典序最小的那个串。这个代表称为“最小循环表示”或“最小表示”。两个序列循环同构当且仅当它们的最小循环表示完全相同。求一个长度为 m 的序列的最小表示时代码使用双指针排除法先把序列看成“原序列接上自身”得到的长度为 2m 的串这样从任意起点读取连续 m 个字符就对应原序列的一个循环旋转。维护两个候选起点初始分别指向第 0 个位置和第 1 个位置。目标是在这些起点中找到从哪个起点开始读出的长度为 m 的串字典序最小。从两个候选起点开始逐字符比较。假设比较到第 k 个字符时第一次出现不同如果前一个候选起点对应的字符更小那么从后一个候选起点到它后面连续若干位置开始的旋转都不可能是最小表示因为它们在第一次不同处已经输给了前一个候选对应的旋转。于是把后一个候选起点直接跳过这一整段移到第一个不同位置之后。如果后一个候选起点对应的字符更小说明后一个候选更优。此时前一个候选起点以及它后面一段起点都不可能是答案于是把前一个候选起点更新为后一个候选起点同时把后一个候选起点跳到至少旧后一个候选起点的下一个位置并且至少跳过刚刚比较过的那一段取二者中较大的位置。如果在比较过程中连续比较了 m 个字符都没有不同说明两个候选起点读出的循环串完全相同或者序列具有周期性。此时当前保存的较优候选起点已经可以作为最小表示的起点停止比较。循环直到第二个候选起点到达原序列长度 m。最终第一个候选起点指向的位置就是字典序最小循环旋转的起点从该位置连续取 m 个字符就是该序列的最小表示。这个双指针过程看似有两层循环但每一轮比较后都会排除掉一段不可能成为最小起点的位置累计排除次数与序列长度同阶因此求一个长度为 m 的序列的最小表示是线性时间。三、把两个最小表示拼接成规范签名对当前字符串的偶数位子序列求出最小表示对奇数位子序列也求出最小表示。然后把“偶数位子序列的最小表示”放在前面“奇数位子序列的最小表示”放在后面拼接成一个新的字符串作为当前原字符串的规范签名。这里顺序必须固定不能交换也不能把两个最小表示排序。原因是偶数位和奇数位在变换中角色不同拼接顺序保留了这种角色信息。同时拼接后的总长度等于原字符串长度所以长度不同的字符串天然会得到不同长度的签名不会被误判为同一类。四、用哈希集合统计不同签名遍历所有给定字符串对每个字符串都生成上述规范签名然后把签名放入一个哈希集合中。哈希集合会自动去重同一个签名无论出现多少次只保留一个。遍历结束后集合中元素的数量就是不同等价类的数量。为什么集合大小就是最少分组数如果两个字符串等价那么它们的偶数位子序列循环同构奇数位子序列也循环同构。循环同构的序列具有相同的最小表示因此两个字符串生成的签名完全相同会落在同一个集合元素中。反过来如果两个字符串生成的签名相同说明偶数位子序列的最小表示相同奇数位子序列的最小表示也相同因此两个子序列分别循环同构。于是可以分别对两个子序列做适当的循环移动使两个字符串变成同一个字符串所以它们等价。等价关系具有传递性每个字符串只对应一个签名所以每个字符串恰好属于一个等价类。每个等价类至少需要一组而把一个等价类整体放成一组又一定满足组内任意两个等价因此最少分组数正好等于等价类数量也就是哈希集合的大小。对于示例中的两个字符串它们虽然表面不同但按奇偶下标拆分后两个子序列分别属于相同的循环同构类因此得到相同的规范签名集合大小为 1输出 1。五、复杂度分析设所有输入字符串的长度总和为 N即 N 等于所有 words[i].length 之和设字符串个数为 M。时间复杂度对每个字符串按奇偶下标拆分耗时与该字符串长度成正比。所有字符串合计 O(N)。对每个字符串的两个子序列分别求最小表示。两个子序列长度之和等于原字符串长度而最小表示算法是线性的所以每个字符串耗时 O(其长度)所有字符串合计 O(N)。把两个最小表示拼接成签名耗时 O(原字符串长度)。所有字符串合计 O(N)。把签名插入哈希集合。按通常哈希表的期望分析计算字符串哈希和插入的期望代价与签名长度成正比所有签名总长度不超过 N因此总期望 O(N)。如果讨论哈希冲突的最坏理论情况可能退化但按常规算法分析使用期望 O(N)。所以总时间复杂度为期望 O(N)其中 N 是所有字符串长度之和。题目给出 N 不超过 500000因此该复杂度足够。额外空间复杂度哈希集合需要保存所有不同的规范签名。每个签名长度等于对应原字符串长度去重后保存的签名总字符数不会超过所有输入字符串总长度 N因此集合占用 O(N)。处理单个字符串时需要临时保存拆出的两个子序列、双指针求最小表示时的临时串以及拼接签名等单个字符串的临时空间与其长度成正比。所有字符串依次处理临时空间可以复用峰值不会超过 O(N)。因此除输入字符串本身外总额外空间复杂度为 O(N)。Go完整代码如下packagemainimport(fmt)// 返回 s 的字典序最小的循环同构串// 时间复杂度 O(|s|)证明见代码末尾的注释funcsmallestRepresentation(s[]byte)[]byte{n:len(s)sappend(s,s...)i:0// 始终指向当前最小子串的首字母下标j:1// 指向需要和 i 比较的子串的首字母下标forjn{// 暴力比较是 i 开头的字典序小还是 j 开头的字典序小k:0forkns[ik]s[jk]{k}ifkn{// s 是个周期字符串周期为 j-i// jd 开头的子串等于 id 开头的子串而这些子串我们之前已经排除了继续遍历不会找到更小的break}ifs[ik]s[jk]{// 注如果求字典序最大改成 // 比如从 i 开始是 aaab从 j 开始是 aaac// 从 i 开始比从 j 开始更小排除 j// 此外// 从 i1 开始比从 j1 开始更小所以从 j1 开始不可能是答案排除// 从 i2 开始比从 j2 开始更小所以从 j2 开始不可能是答案排除// ……// 从 ik 开始比从 jk 开始更小所以从 jk 开始不可能是答案排除// 所以下一个「可能是答案」的开始位置是 jk1jk1}else{// 从 j 开始比从 i 开始更小更新 ij也意味着我们排除了 i// 此外// 从 j1 开始比从 i1 开始更小所以从 i1 开始不可能是答案排除// 从 j2 开始比从 i2 开始更小所以从 i2 开始不可能是答案排除// ……// 从 jk 开始比从 ik 开始更小所以从 ik 开始不可能是答案排除// 所以把 j 跳到 ik1不过这可能比 j1 小所以与 j1 取 max// 综上所述下一个「可能是答案」的开始位置是 max(j1, ik1)i,jj,max(j,ik)1}// 每次要么排除 k1 个与 i 相关的位置这样的位置至多 n 个要么排除 k1 个与 j 相关的位置这样的位置至多 n 个// 所以上面关于 k 的循环∑k 2n所以二重循环的总循环次数是 O(n) 的}returns[i:in]}funcminimumGroups(words[]string)(ansint){set:map[string]struct{}{}for_,word:rangewords{// 按照下标的奇偶性分组groups:[2][]byte{}fori,ch:rangeword{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)}funcmain(){words:[]string{ntgwz,zwntg}result:minimumGroups(words)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defsmallest_representation(s:str)-str: 返回字符串 s 的字典序最小的循环同构串。 时间复杂度 O(|s|)。 nlen(s)ifn0:returnssss# 相当于 Go 里的 s append(s, s...)i0# 始终指向当前最小子串的首字母下标j1# 指向需要和 i 比较的子串的首字母下标whilejn:k0# 暴力比较以 i 开头和以 j 开头的子串哪个字典序更小whileknandss[ik]ss[jk]:k1ifkn:# s 是周期字符串周期为 j-i# 继续遍历不会找到更小的breakifss[ik]ss[jk]:# 从 i 开始比从 j 开始更小排除 j 到 jk 这些起点jk1else:# 从 j 开始比从 i 开始更小更新 ij# 并排除 i 到 ik 这些起点i,jj,max(j,ik)1returnss[i:in]defminimum_groups(words)-int:seenset()forwordinwords:# 按照下标的奇偶性分组groups[,]foridx,chinenumerate(word):groups[idx%2]ch# 分别计算偶数组和奇数组的最小表示ssmallest_representation(groups[0])tsmallest_representation(groups[1])# 用「偶数组最小表示 奇数组最小表示」作为等价类标识seen.add(st)returnlen(seen)defmain():words[ntgwz,zwntg]resultminimum_groups(words)print(result)if__name____main__:main()C完整代码如下#includebits/stdc.husingnamespacestd;// 返回 s 的字典序最小的循环同构串// 时间复杂度 O(|s|)stringsmallestRepresentation(conststrings){intn(int)s.size();if(n0)return;string ssss;// 相当于 Go 里的 s append(s, s...)inti0;// 始终指向当前最小子串的首字母下标intj1;// 指向需要和 i 比较的子串的首字母下标while(jn){// 暴力比较是 i 开头的字典序小还是 j 开头的字典序小intk0;while(knss[ik]ss[jk]){k;}if(kn){// s 是个周期字符串周期为 j-i// jd 开头的子串等于 id 开头的子串而这些子串我们之前已经排除了// 继续遍历不会找到更小的break;}if(ss[ik]ss[jk]){// 注如果求字典序最大改成 // 比如从 i 开始是 aaab从 j 开始是 aaac// 从 i 开始比从 j 开始更小排除 j// 此外// 从 i1 开始比从 j1 开始更小所以从 j1 开始不可能是答案排除// 从 i2 开始比从 j2 开始更小所以从 j2 开始不可能是答案排除// ……// 从 ik 开始比从 jk 开始更小所以从 jk 开始不可能是答案排除// 所以下一个「可能是答案」的开始位置是 jk1jk1;}else{// 从 j 开始比从 i 开始更小更新 ij也意味着我们排除了 i// 此外// 从 j1 开始比从 i1 开始更小所以从 i1 开始不可能是答案排除// 从 j2 开始比从 i2 开始更小所以从 i2 开始不可能是答案排除// ……// 从 jk 开始比从 ik 开始更小所以从 ik 开始不可能是答案排除// 所以把 j 跳到 ik1不过这可能比 j1 小所以与 j1 取 max// 综上所述下一个「可能是答案」的开始位置是 max(j1, ik1)intnewJmax(j,ik)1;ij;jnewJ;}// 每次要么排除 k1 个与 i 相关的位置这样的位置至多 n 个要么排除 k1 个与 j 相关的位置这样的位置至多 n 个// 所以上面关于 k 的循环∑k 2n所以二重循环的总循环次数是 O(n) 的}returnss.substr(i,n);}intminimumGroups(constvectorstringwords){setstringseen;for(conststringword:words){// 按照下标的奇偶性分组string groups[2];for(intidx0;idx(int)word.size();idx){groups[idx%2].push_back(word[idx]);}// 分别计算偶数组和奇数组的最小表示string ssmallestRepresentation(groups[0]);string tsmallestRepresentation(groups[1]);// 用「偶数组最小表示 奇数组最小表示」作为等价类标识seen.insert(st);}return(int)seen.size();}intmain(){vectorstringwords{ntgwz,zwntg};intresultminimumGroups(words);coutresultendl;return0;}