2026-05-16统计残差前缀。用go语言给定一个只包含小写英文字母的字符串 s。对 s 的每一个非空前缀从开头开始截取到某个位置的子串记这个前缀的长度为 L且它包含的不同字符种类数为 K。若满足 K L % 3则这个前缀称为“残差前缀”。问s 中一共有多少个这样的残差前缀。1 s.length 100。s 仅包含小写英文字母。输入: s “abc”。输出: 2。解释:前缀 “a” 有 1 个不同字符且长度模 3 为 1因此它是一个残差前缀。前缀 “ab” 有 2 个不同字符且长度模 3 为 2因此它是一个残差前缀。前缀 “abc” 不满足条件因此不是残差前缀。因此答案是 2。题目来自力扣3803。分步骤详细描述第一步遍历第一个字符字符 ‘a’对应前缀 “a”当前遍历位置i0字符是a把字符a加入字符集合a-a0将整数1左移0位还是1用或运算存入set此时set 1二进制000...0001统计set中1的个数得到不同字符数cnt1即K1判断字符种类数是否等于31≠3不执行中断核心条件判断前缀长度L i1 1L%3 1%3 1cnt(1) 1条件成立残差前缀数量ans加1此时ans1。第二步遍历第二个字符字符 ‘b’对应前缀 “ab”当前遍历位置i1字符是b把字符b加入字符集合b-a1将整数1左移1位值为2和原有set做或运算此时set 1 | 2 3二进制000...0011统计set中1的个数得到不同字符数cnt2即K2判断字符种类数是否等于32≠3不执行中断核心条件判断前缀长度L i1 2L%3 2%3 2cnt(2) 2条件成立残差前缀数量ans加1此时ans2。第三步遍历第三个字符字符 ‘c’对应前缀 “abc”当前遍历位置i2字符是c把字符c加入字符集合c-a2将整数1左移2位值为4和原有set做或运算此时set 3 | 4 7二进制000...0111统计set中1的个数得到不同字符数cnt3即K3判断字符种类数是否等于333直接跳出循环不再执行后续逻辑本次遍历不做任何条件判断和计数。第四步函数返回结果循环结束函数返回ans的值最终结果为2与题目要求一致。时间复杂度与额外空间复杂度分析1. 时间复杂度代码核心逻辑是单次遍历字符串遍历次数等于字符串长度n本题n3遍历内部的位运算、统计1的个数、条件判断都是常数时间操作O(1)总时间复杂度O(n)n为字符串长度。2. 额外空间复杂度代码仅使用了ans、set、cnt、i、ch这几个固定数量的变量没有使用随字符串长度变化的数组、切片等动态数据结构占用空间与输入长度无关总额外空间复杂度O(1)常数空间。总结执行过程依次遍历字符串的每个字符逐一生成前缀、统计字符种类、判断残差条件满足则计数字符种类达到3时提前终止循环时间复杂度为线性复杂度O(n)效率极高额外空间复杂度为常数级O(1)几乎不占用额外内存。Go完整代码如下packagemainimport(fmtmath/bits)funcresiduePrefixes(sstring)(ansint){set:0fori,ch:ranges{set|1(ch-a)// 把 ch 添加到 set 中cnt:bits.OnesCount(uint(set))ifcnt3{break}ifcnt(i1)%3{ans}}return}funcmain(){s:abcresult:residuePrefixes(s)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defresidue_prefixes(s:str)-int:ans0bit_set0fori,chinenumerate(s):# Add ch to the bit setbit_set|1(ord(ch)-ord(a))cntbin(bit_set).count(1)# Count number of set bitsifcnt3:breakifcnt(i1)%3:ans1returnansdefmain():sabcresultresidue_prefixes(s)print(result)if__name____main__:main()C完整代码如下#includeiostream#includestring#includebitsetintresiduePrefixes(conststd::strings){intans0;intset0;for(inti0;is.length();i){// Add ch to the bit setset|1(s[i]-a);// Count number of set bitsintcnt__builtin_popcount(set);if(cnt3){break;}if(cnt(i1)%3){ans;}}returnans;}intmain(){std::string sabc;intresultresiduePrefixes(s);std::coutresultstd::endl;return0;}
2026-05-16：统计残差前缀。用go语言，给定一个只包含小写英文字母的字符串 s。 对 s 的每一个非空前缀（从开头开始截取到某个位置的子串），记这个前缀的长度为 L，且它包含的不同字符种类数为
2026-05-16统计残差前缀。用go语言给定一个只包含小写英文字母的字符串 s。对 s 的每一个非空前缀从开头开始截取到某个位置的子串记这个前缀的长度为 L且它包含的不同字符种类数为 K。若满足 K L % 3则这个前缀称为“残差前缀”。问s 中一共有多少个这样的残差前缀。1 s.length 100。s 仅包含小写英文字母。输入: s “abc”。输出: 2。解释:前缀 “a” 有 1 个不同字符且长度模 3 为 1因此它是一个残差前缀。前缀 “ab” 有 2 个不同字符且长度模 3 为 2因此它是一个残差前缀。前缀 “abc” 不满足条件因此不是残差前缀。因此答案是 2。题目来自力扣3803。分步骤详细描述第一步遍历第一个字符字符 ‘a’对应前缀 “a”当前遍历位置i0字符是a把字符a加入字符集合a-a0将整数1左移0位还是1用或运算存入set此时set 1二进制000...0001统计set中1的个数得到不同字符数cnt1即K1判断字符种类数是否等于31≠3不执行中断核心条件判断前缀长度L i1 1L%3 1%3 1cnt(1) 1条件成立残差前缀数量ans加1此时ans1。第二步遍历第二个字符字符 ‘b’对应前缀 “ab”当前遍历位置i1字符是b把字符b加入字符集合b-a1将整数1左移1位值为2和原有set做或运算此时set 1 | 2 3二进制000...0011统计set中1的个数得到不同字符数cnt2即K2判断字符种类数是否等于32≠3不执行中断核心条件判断前缀长度L i1 2L%3 2%3 2cnt(2) 2条件成立残差前缀数量ans加1此时ans2。第三步遍历第三个字符字符 ‘c’对应前缀 “abc”当前遍历位置i2字符是c把字符c加入字符集合c-a2将整数1左移2位值为4和原有set做或运算此时set 3 | 4 7二进制000...0111统计set中1的个数得到不同字符数cnt3即K3判断字符种类数是否等于333直接跳出循环不再执行后续逻辑本次遍历不做任何条件判断和计数。第四步函数返回结果循环结束函数返回ans的值最终结果为2与题目要求一致。时间复杂度与额外空间复杂度分析1. 时间复杂度代码核心逻辑是单次遍历字符串遍历次数等于字符串长度n本题n3遍历内部的位运算、统计1的个数、条件判断都是常数时间操作O(1)总时间复杂度O(n)n为字符串长度。2. 额外空间复杂度代码仅使用了ans、set、cnt、i、ch这几个固定数量的变量没有使用随字符串长度变化的数组、切片等动态数据结构占用空间与输入长度无关总额外空间复杂度O(1)常数空间。总结执行过程依次遍历字符串的每个字符逐一生成前缀、统计字符种类、判断残差条件满足则计数字符种类达到3时提前终止循环时间复杂度为线性复杂度O(n)效率极高额外空间复杂度为常数级O(1)几乎不占用额外内存。Go完整代码如下packagemainimport(fmtmath/bits)funcresiduePrefixes(sstring)(ansint){set:0fori,ch:ranges{set|1(ch-a)// 把 ch 添加到 set 中cnt:bits.OnesCount(uint(set))ifcnt3{break}ifcnt(i1)%3{ans}}return}funcmain(){s:abcresult:residuePrefixes(s)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defresidue_prefixes(s:str)-int:ans0bit_set0fori,chinenumerate(s):# Add ch to the bit setbit_set|1(ord(ch)-ord(a))cntbin(bit_set).count(1)# Count number of set bitsifcnt3:breakifcnt(i1)%3:ans1returnansdefmain():sabcresultresidue_prefixes(s)print(result)if__name____main__:main()C完整代码如下#includeiostream#includestring#includebitsetintresiduePrefixes(conststd::strings){intans0;intset0;for(inti0;is.length();i){// Add ch to the bit setset|1(s[i]-a);// Count number of set bitsintcnt__builtin_popcount(set);if(cnt3){break;}if(cnt(i1)%3){ans;}}returnans;}intmain(){std::string sabc;intresultresiduePrefixes(s);std::coutresultstd::endl;return0;}
