You are given a 0-indexed binary string s which represents the types of buildings along a street where:


	s[i] = '0' denotes that the ith building is an office and
	s[i] = '1' denotes that the ith building is a restaurant.


As a city official, you would like to select 3 buildings for random inspection. However, to ensure variety, no two consecutive buildings out of the selected buildings can be of the same type.


	For example, given s = "001101", we cannot select the 1st, 3rd, and 5th buildings as that would form "011" which is not allowed due to having two consecutive buildings of the same type.


Return the number of valid ways to select 3 buildings.

&nbsp;
Example 1:

Input: s = "001101"
Output: 6
Explanation: 
The following sets of indices selected are valid:
- [0,2,4] from "001101" forms "010"
- [0,3,4] from "001101" forms "010"
- [1,2,4] from "001101" forms "010"
- [1,3,4] from "001101" forms "010"
- [2,4,5] from "001101" forms "101"
- [3,4,5] from "001101" forms "101"
No other selection is valid. Thus, there are 6 total ways.


Example 2:

Input: s = "11100"
Output: 0
Explanation: It can be shown that there are no valid selections.


&nbsp;
Constraints:


	3 &lt;= s.length &lt;= 105
	s[i] is either '0' or '1'.


class Solution:
    def numberOfWays(self, s: str) -> int:
        
        temp = []
        c0 = 0
        c1 = 0
        for char in s :
            if char == "0" :
                c0+=1
            else:
                c1+=1
            temp.append([c0,c1])
            
        total0 = c0
        total1 = c1
        
        
        count = 0
        for i in range(1, len(s)-1) :
            
            if s[i] == "0" :
                m1 = temp[i-1][1]
                m2 = total1 - temp[i][1]
                count += m1*m2
                
            else:
                m1 = temp[i-1][0]
                m2 = total0 - temp[i][0]
                count += m1*m2
        return count
                
        
class Solution
{
    public long numberOfWays(String s)
    {
        int zero = 0; // Individual zeroes count
        long zeroOne = 0; // Number of combinations of 01s
        int one = 0; // Individual ones count
        long oneZero = 0; // Number of combinations of 10s
        long tot = 0; // Final answer
        for(char ch : s.toCharArray())
        {
            if(ch == '0')
            {
                zero++;
                if(one > 0)
                    oneZero += one; // Each of the previously found 1s can pair up with the current 0 to form 10
                if(zeroOne > 0)
                    tot += zeroOne; // Each of the previously formed 01 can form a triplet with the current 0 to form 010
            }
            else
            {
                one++;
                if(zero > 0)
                    zeroOne += zero; // Each of the previously found 0s can pair to form 01
                if(oneZero > 0)
                    tot += oneZero; // Each of the previously formed 10 can form 101
            }
        }
        return tot;
    }
}
class Solution {
public:
    long long numberOfWays(string s) {
        long long a=0,b=0,ans=0;        // a and b are the number of occurances of '1' and '0' after the current building respectively.
        for(int i=0;i<s.length();i++){
            if(s[i]=='1')
                a++;
            else
                b++;
        }
        long long c=0,d=0;              // c and d are the number of occurances of '1' and '0' before the current building respectively.
        for(int i=0;i<s.length();i++){
            if(s[i]=='1'){               // Counting the sequences of "010"
                ans+=(d*b);
                a--;
                c++;
            }
            else{                        // Counting the sequences of "101"
                ans+=(a*c);
                b--;
                d++;
            }
        }
        return ans;
    }
};
var numberOfWays = function(s) {
    const len = s.length;
    const prefix = new Array(len).fill(0).map(() => new Array(2).fill(0));
    for(let i = 0; i < len; i++) {
        const idx = s[i] == '1' ? 1 : 0;
        if(i == 0) prefix[i][idx]++;
        else {
            prefix[i] = Array.from(prefix[i-1]);
            prefix[i][idx]++;
        }
    }
    let ans = 0;
    for(let i = 1; i < len - 1; i++) {
        const c = s[i] == '1' ? 0 : 1;
        ans += (prefix.at(-1)[c] - prefix[i][c]) * prefix[i-1][c];
    }
    return ans;
};
Number of Ways to Select Buildings