题意

给你一个下标从 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 <= 105
s[i] 要么是 '0' ，要么是 '1' 。

分析

按照上述题意，可知主要分成两种情况101与010。因此我们可以采用的方法包括dfs，以及分别计算0和1的个数。

题解

DFS（统计出现101或者010的个数）

class Solution {
    int ans = 0;
    public long numberOfWays(String s) {
        if(s==null||s.length()==0) return 0;
        numberOfWaysSub(s,0,new ArrayList<Integer>());
        return ans;
    }

    public void numberOfWaysSub(String s,int index, List<Integer> list){
        if(list.size()==3){
            ans++;
            return;
        }
        for(int i = index;i<s.length();i++){
            // 控制列表的元素符合要求
            if(list.size()!=0&&s.charAt(list.get(list.size()-1))==s.charAt(i)) continue;
            list.add(i);
            numberOfWaysSub(s,i+1,list);
            list.remove(list.size()-1);
        }
    }
}

DP（分别计算0和1的个数，则如果当前节点为0，计算其前缀1的个数与后缀1的个数，相乘就是101的个数，如果节点为1则有相似逻辑）

class Solution {
    public long numberOfWays(String s) {
        if(s==null||s.length()==0) return 0L;
       // 分别表示前缀0与1的个数
        long[] n0 = new long[s.length()];
        long[] n1 = new long[s.length()];
        if(s.charAt(0)=='0') {
            n0[0] = 1;
            n1[0] = 0;
        }else{
            n0[0] = 0;
            n1[0] = 1;
        }
        for(int i = 1;i<s.length();i++){
            if(s.charAt(i)=='0') {
                n0[i]=n0[i-1]+1;
                n1[i] = n1[i-1];
            }else{
                n1[i]=n1[i-1]+1;
                n0[i] = n0[i-1];
            }
        }
        long ans = 0;
        for(int i = 1;i<s.length()-1;i++){
            if(s.charAt(i)=='0'){
                // 当前节点为0，需要计算前后1的个数
                long preNumber = n1[i-1];
                long postNumber = n1[s.length()-1] - n1[i];
                ans+=preNumber*postNumber;
            }else{
                // 当前节点为1，需要计算前后0的个数
                long preNumber = n0[i-1];
                long postNumber = n0[s.length()-1]-n0[i];
                ans+=preNumber*postNumber;
            }
        }
        return ans;
    }
}

DP2（将当前节点作为结尾节点，如果当前节点为1，计算其前缀10的个数，如果当前节点为0，计算其前缀01的个数）

class Solution {
    public long numberOfWays(String s) {
        long ans = 0;
       // 前缀01的个数，如果当前节点为1，则01的个数新增前缀为0的数据（组成01）
        long number01 = 0;
       // 前缀10的个数，如果当前节点为0，则01的个数新增前缀为1的数据（组成10）
        long number10 = 0;
        long n0 = 0;
        long n1 = 0;
        for(int i = 0;i<s.length();i++){
            if(s.charAt(i)=='0'){
                n0++;
                number10+=n1;
                ans+=number01;
            }else{
                n1++;
                number01+=n0;
                ans+=number10;
            }
        }
        return ans;
    }
}