如何优化统计二进制字符串有效长度3子序列的算法时间复杂度

算力阿峰

2026-10-2

优化方案

核心思路

合法的长度为3、相邻字符互不相同的二进制子序列，仅存在两种固定模式：010 和 101。因为相邻字符要求不同，所以首尾字符一定相同，中间字符与首尾相反，我们只需要分别统计两种模式的子序列数量相加即可得到最终结果。
统计逻辑如下：

先统计字符串中0的总数量total0、1的总数量total1
遍历字符串的每个字符作为子序列的中间位，同时维护遍历到当前位置之前出现的0的数量left0、1的数量left1：
- 如果当前字符是1：它可以作为010模式的中间位，贡献的子序列数量 = 左边0的数量 * 右边剩余0的数量，即 left0 * (total0 - left0)
- 如果当前字符是0：它可以作为101模式的中间位，贡献的子序列数量 = 左边1的数量 * 右边剩余1的数量，即 left1 * (total1 - left1)
所有位置的贡献值累加就是最终答案

优化后代码

public static long process(String s) {
    long result = 0;
    int n = s.length();
    if (n < 3) return 0;
    // 统计字符串中0和1的总数量
    int total0 = 0, total1 = 0;
    for (int i = 0; i < n; i++) {
        if (s.charAt(i) == '0') total0++;
        else total1++;
    }
    int left0 = 0, left1 = 0;
    for (int i = 0; i < n; i++) {
        char c = s.charAt(i);
        if (c == '1') {
            // 计算当前1作为中间位贡献的010模式数量
            result += (long) left0 * (total0 - left0);
            left1++;
        } else {
            // 计算当前0作为中间位贡献的101模式数量
            result += (long) left1 * (total1 - left1);
            left0++;
        }
    }
    return result;
}