Welcome to Subscribe On Youtube
2222. Number of Ways to Select Buildings
Description
You are given a 0indexed binary string s
which represents the types of buildings along a street where:
s[i] = '0'
denotes that thei^{th}
building is an office ands[i] = '1'
denotes that thei^{th}
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 the1^{st}
,3^{rd}
, and5^{th}
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.
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.
Constraints:
3 <= s.length <= 10^{5}
s[i]
is either'0'
or'1'
.
Solutions

class Solution { public long numberOfWays(String s) { int n = s.length(); int cnt0 = 0; for (char c : s.toCharArray()) { if (c == '0') { ++cnt0; } } int cnt1 = n  cnt0; long ans = 0; int c0 = 0, c1 = 0; for (char c : s.toCharArray()) { if (c == '0') { ans += c1 * (cnt1  c1); ++c0; } else { ans += c0 * (cnt0  c0); ++c1; } } return ans; } }

class Solution { public: long long numberOfWays(string s) { int n = s.size(); int cnt0 = 0; for (char& c : s) cnt0 += c == '0'; int cnt1 = n  cnt0; int c0 = 0, c1 = 0; long long ans = 0; for (char& c : s) { if (c == '0') { ans += c1 * (cnt1  c1); ++c0; } else { ans += c0 * (cnt0  c0); ++c1; } } return ans; } };

class Solution: def numberOfWays(self, s: str) > int: n = len(s) cnt0 = s.count("0") cnt1 = n  cnt0 c0 = c1 = 0 ans = 0 for c in s: if c == "0": ans += c1 * (cnt1  c1) c0 += 1 else: ans += c0 * (cnt0  c0) c1 += 1 return ans

func numberOfWays(s string) int64 { n := len(s) cnt0 := strings.Count(s, "0") cnt1 := n  cnt0 c0, c1 := 0, 0 ans := 0 for _, c := range s { if c == '0' { ans += c1 * (cnt1  c1) c0++ } else { ans += c0 * (cnt0  c0) c1++ } } return int64(ans) }