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

福大大架构师每日一题

发布于 2026-05-20 13:40:19

780

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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++完整代码如下：

#include <iostream>
#include <string>
#include <bitset>

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;
}