[2222] 选择建筑的方案数

给你一个下标从 0 开始的二进制字符串 s ，它表示一条街沿途的建筑类型，其中：

s[i] = '0' 表示第 i 栋建筑是一栋办公楼，

s[i] = '1' 表示第 i 栋建筑是一间餐厅。

作为市政厅的官员，你需要随机 选择 3 栋建筑。然而，为了确保多样性，选出来的 3 栋建筑 相邻 的两栋不能是同一类型。

比方说，给你 s = "001101" ，我们不能选择第 1 ，3 和 5 栋建筑，因为得到的子序列是 "011" ，有相邻两栋建筑是同一类型，所以 不合 题意。

请你返回可以选择 3 栋建筑的 有效方案数 。

示例 1：

输入：s = "001101"

输出：6

解释：

以下下标集合是合法的：

• [0,2,4] ，从 "001101" 得到 "010"
• [0,3,4] ，从 "001101" 得到 "010"
• [1,2,4] ，从 "001101" 得到 "010"
• [1,3,4] ，从 "001101" 得到 "010"
• [2,4,5] ，从 "001101" 得到 "101"
• [3,4,5] ，从 "001101" 得到 "101"

没有别的合法选择，所以总共有 6 种方法。

示例 2：

输入：s = "11100"

输出：0

解释：没有任何符合题意的选择。

提示：

3 <= s.length <= 10^5

s[i] 要么是 '0' ，要么是 '1' 。

这道题直觉想到了三指针暴力遍历，代码如下：

// Over Time Limit
function numberOfWays(s: string): number {
  let res = 0;
  const len = s.length;
  for (let i = 0; i < len - 2; i++) {
    for (let j = i + 1; j < len - 1; j++) {
      if (s[i] === s[j]) continue;
      for (let k = j + 1; k < len; k++) {
        if (s[j] !== s[k]) res += 1;
      }
    }
  }
  return res;
}

但是超时了，需要有更精妙的解法。

注意到，符合要求的长度为 3 的子序列只有两种情况，010 和 101，所以只需要遍历中间元素，统计两侧为 0 或者 1 的个数，将左右两侧的情况相乘，即可得到 010 和 101 的个数。

我们可以遍历一次字符串，获取到0和1的总个数。并在第二次遍历时，分两种情况判断，若当前中间元素为0，则判断两侧为1的个数，若当前中间元素为1，则判断两侧为0的个数。相乘两侧的情况数，最后将两种情况相加即可。整体时间复杂度就可降到 O(n)。

具体实现如下：

function numberOfWays(s: string): number {
  const len = s.length;

  // 统计字符串中 0 和 1 的个数
  const count1 = s.split('1').length - 1;
  const count0 = len - count1;

  let res = 0;

  // 遍历到当前位置 1 的个数
  let curCount1 = 0;

  for (let i = 0; i < len; i++) {
    if (s[i] === '1') {
      // 左侧 0 的个数，等于当前位置总数减去当前位置 1 的个数
      const cntL0 = i - curCount1;
      // 右侧 0 的个数，等于总 0 个数减去左侧 0 的个数
      const cntR0 = count0 - cntL0;
      res += cntL0> cntR0;

      curCount1 += 1;
    } else {
      // 左侧 1 的个数
      const cntL1 = curCount1;
      // 右侧 1 的个数，等于总 1 个数减去左侧 1 的个数
      const cntR1 = count1 - cntL1;
      res += cntL1> cntR1;
    }
  }
  return res;
}