2026-10-27：统计有效前缀数目。用go语言，给定一个只包含字符 0 和 1 的字符串 s。对于字符串从头开始的每一个连续片段（即前缀），判断

2026-10-27：统计有效前缀数目。用go语言，给定一个只包含字符 0 和 1 的字符串 s。对于字符串从头开始的每一个连续片段（即前缀），判断这个片段中的字符经过重新排列后，能否形成相邻字符都不相同的交替序列。若可以，则把该前缀视为满足条件。要求统计字符串 s 中满足条件的前缀总数。

换句话说，对每个前缀分别查看其中 0 和 1 的数量：只要这两种字符的数量相差不超过 1，这个前缀就可以重新排成交替形式；否则不行。最后返回所有满足该条件的前缀数量。

1 <= s.length <= 100。

s 仅由 '0' 和 '1' 组成。

输入： s = "00101"。

输出： 3。

解释：

有效的前缀是：

"0"：它已经是一个交替字符串。

"001"：可以被重新排列成 "010"，这是一个交替字符串。

"00101"：可以被重新排列成 "01010"，这是一个交替字符串。

因此，答案是 3。

题目来自力扣4006。

大体步骤如下：

1. 1.初始化统计变量
   准备一个答案变量，用来记录满足条件的前缀数量，初始为 0。
   再准备两个计数位置，分别记录当前前缀中字符0的个数和字符1的个数，初始都为 0。

2. 2.从左到右逐个字符扫描字符串
   程序按顺序读取字符串中的每一个字符。每读取一个字符，就把它归入0或1，并让对应的计数加 1。
   因为是从头开始顺序扫描，所以每读到一个字符时，当前的计数状态正好对应“从字符串开头到当前位置”的这个前缀。

3. 3.每形成一个前缀就立即判断是否有效
   对当前前缀，计算其中0的个数与1的个数之差的绝对值。
   如果这个绝对值不超过 1，说明两种字符的数量相差最多 1 个，可以重新排列成相邻字符都不相同的交替序列，因此当前前缀有效，答案加 1。
   如果差的绝对值大于 1，说明某一种字符比另一种多出至少 2 个，无法排成交替序列，当前前缀无效，答案不变。

4. 4.判断条件的含义
   一个只含0和1的字符串要能重排成交替序列，最终形式只能是类似010101...或101010...。
   在这种序列中，两种字符的数量最多只能相差 1。
   反过来，如果两种字符数量差不超过 1，也一定可以通过排列让它们交替出现。
   所以“当前前缀中0和1的数量差绝对值不超过 1”就是该前缀能否重排成交替序列的充要条件。

5. 5.继续扫描直到字符串结束
   每读入一个字符，就更新计数并判断一次当前前缀。程序不会对每个前缀重新从头统计，而是利用前面已经统计好的结果继续累加，因此效率较高。

6. 6.结合示例s = "00101"逐步看

• • 前缀"0"：0有 1 个，1有 0 个，差为 1，不超过 1，有效，答案变为 1。

• • 前缀"00"：0有 2 个，1有 0 个，差为 2，无效，答案仍为 1。

• • 前缀"001"：0有 2 个，1有 1 个，差为 1，有效，答案变为 2。

• • 前缀"0010"：0有 3 个，1有 1 个，差为 2，无效，答案仍为 2。

• • 前缀"00101"：0有 3 个，1有 2 个，差为 1，有效，答案变为 3。
  最终返回 3。

7.最终结果
所有满足条件的前缀是"0"、"001"、"00101"，共 3 个。

复杂度分析：

• •总时间复杂度：字符串长度为n时，只需要从左到右扫描一遍，每个字符进行常数次计数和比较操作，因此总时间复杂度是O(n)。

• •总额外空间复杂度：只使用了两个计数变量、答案变量和少量常数级辅助变量，没有随字符串长度增长的额外结构，因此额外空间复杂度是O(1)。

package main

 import (
    "fmt"
)

 func countValidPrefixes(s string) (ans int) {
    cnt := [2]int{}
    for _, ch := range s {
        cnt[ch-'0']++
        if abs(cnt[0]-cnt[1]) <= 1 {
            ans++
        }
    }
    return
}

 func abs(x int)int {
    if x < 0 {
        return -x
    }
    return x
}

 func main() {
    s := "00101"
    result := countValidPrefixes(s)
    fmt.Println(result)
}

Python完整代码如下：

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

 def count_valid_prefixes(s: str) -> int:
    cnt = [0, 0]
    ans = 0

     for ch in s:
        cnt[int(ch)] += 1
        if abs(cnt[0] - cnt[1]) <= 1:
            ans += 1

     return ans

 def main():
    s = "00101"
    result = count_valid_prefixes(s)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代码如下：

  

  

using namespace std;

 int countValidPrefixes(conststring& s) {
    int cnt[2] = {0, 0};
    int ans = 0;

     for (char ch : s) {
        cnt[ch - '0']++;
        if (abs(cnt[0] - cnt[1]) <= 1) {
            ans++;
        }
    }

     return ans;
}

 int main() {
    string s = "00101";
    int result = countValidPrefixes(s);
    cout << result << endl;
    return0;
}

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