2026-05-16：统计残差前缀。用go语言，给定一个只包含小写英文字母的字符串 s。 对 s 的每一个非空前缀（从开头开始截取到某个位置的子串

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”）

1. 当前遍历位置i=0，字符是a；

2. 把字符a加入字符集合：a-'a'=0，将整数1左移0位（还是1），用或运算存入set，此时set = 1（二进制：000...0001）；

3. 统计set中1的个数，得到不同字符数cnt=1（即K=1）；

4. 判断字符种类数是否等于3：1≠3，不执行中断；

5. 核心条件判断：
前缀长度L = i+1 = 1，L%3 = 1%3 = 1；
cnt(1) = 1，条件成立；

6. 残差前缀数量ans加1，此时ans=1。

第二步：遍历第二个字符（字符 ‘b’，对应前缀 “ab”）

1. 当前遍历位置i=1，字符是b；

2. 把字符b加入字符集合：b-'a'=1，将整数1左移1位（值为2），和原有set做或运算，此时set = 1 | 2 = 3（二进制：000...0011）；

3. 统计set中1的个数，得到不同字符数cnt=2（即K=2）；

4. 判断字符种类数是否等于3：2≠3，不执行中断；

5. 核心条件判断：
前缀长度L = i+1 = 2，L%3 = 2%3 = 2；
cnt(2) = 2，条件成立；

6. 残差前缀数量ans加1，此时ans=2。

第三步：遍历第三个字符（字符 ‘c’，对应前缀 “abc”）

1. 当前遍历位置i=2，字符是c；

2. 把字符c加入字符集合：c-'a'=2，将整数1左移2位（值为4），和原有set做或运算，此时set = 3 | 4 = 7（二进制：000...0111）；

3. 统计set中1的个数，得到不同字符数cnt=3（即K=3）；

4. 判断字符种类数是否等于3：3=3，直接跳出循环，不再执行后续逻辑；

5. 本次遍历不做任何条件判断和计数。

第四步：函数返回结果

循环结束，函数返回ans的值，最终结果为2，与题目要求一致。

时间复杂度与额外空间复杂度分析 1. 时间复杂度

• 代码核心逻辑是单次遍历字符串，遍历次数等于字符串长度n（本题n=3）；

• 遍历内部的位运算、统计1的个数、条件判断都是常数时间操作（O(1)）；

• 总时间复杂度：O(n)（n为字符串长度）。

2. 额外空间复杂度

• 代码仅使用了ans、set、cnt、i、ch这几个固定数量的变量；

• 没有使用随字符串长度变化的数组、切片等动态数据结构，占用空间与输入长度无关；

• 总额外空间复杂度：O(1)（常数空间）。

总结

1. 执行过程依次遍历字符串的每个字符，逐一生成前缀、统计字符种类、判断残差条件，满足则计数，字符种类达到3时提前终止循环；

2. 时间复杂度为线性复杂度O(n)，效率极高；

3. 额外空间复杂度为常数级O(1)，几乎不占用额外内存。

Go完整代码如下：

package main

 import (
    "fmt"
    "math/bits"
)

 func residuePrefixes(s string) (ans int) {
    set := 0
    for i, ch := range s {
        set |= 1 << (ch - 'a') // 把 ch 添加到 set 中
        cnt := bits.OnesCount(uint(set))
        if cnt == 3 {
            break
        }
        if cnt == (i+1)%3 {
            ans++
        }
    }
    return
}

 func main() {
    s := "abc"
    result := residuePrefixes(s)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 def residue_prefixes(s: str) -> int:
    ans = 0
    bit_set = 0
    for i, ch in enumerate(s):
        # Add ch to the bit set
        bit_set |= 1 << (ord(ch) - ord('a'))
        cnt = bin(bit_set).count('1')  # Count number of set bits
        if cnt == 3:
            break
        if cnt == (i + 1) % 3:
            ans += 1
    return ans

 def main():
    s = "abc"
    result = residue_prefixes(s)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代码如下：

  

  


 int residuePrefixes(const std::string& s) {
    int ans = 0;
    int set = 0;

     for (int i = 0; i < s.length(); i++) {
        // Add ch to the bit set
        set |= 1 << (s[i] - 'a');

         // Count number of set bits
        int cnt = __builtin_popcount(set);

         if (cnt == 3) {
            break;
        }

         if (cnt == (i + 1) % 3) {
            ans++;
        }
    }

     return ans;
}

 int main() {
    std::string s = "abc";
    int result = residuePrefixes(s);
    std::cout << result << std::endl;
    return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。