Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2222.html
2222. Number of Ways to Select Buildings (Medium)
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'
.
Solution 1. DP
Let dp[len][c]
be the count of alternating subsequences of length len
ending with character '0' + c'
. The answer is dp[3][0] + dp[3][1]
.
We can scan the array from left to right and compute these dp[len][c]
values.
For each dp[len][c]
, its count should increase by dp[len  1][1  c]
, i.e. prepending subsequences of length len  1
ending with a different character.

// OJ: https://leetcode.com/problems/numberofwaystoselectbuildings/ // Time: O(N) // Space: O(1) class Solution { public: long long numberOfWays(string s) { long dp[4][2] = {}; dp[0][0] = dp[0][1] = 1; for (int i = 0; i < s.size(); ++i) { for (int len = 1; len <= 3; ++len) { dp[len][s[i]  '0'] += dp[len  1][1  (s[i]  '0')]; // for this s[i], we can prepend subsequences of length `len1` ending with a different character to it. } } return dp[3][0] + dp[3][1]; } };

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 ############ # 2222. Number of Ways to Select Buildings # https://leetcode.com/problems/numberofwaystoselectbuildings/ class Solution: def numberOfWays(self, s: str) > int: rZero, rOne = s.count("0"), s.count("1") lZero = lOne = 0 res = 0 for x in s: if x == "1": lOne += 1 res += lZero * rZero rOne = 1 else: lZero += 1 res += lOne * rOne rZero = 1 return res

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; } }

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) }
Discuss
https://leetcode.com/problems/numberofwaystoselectbuildings/discuss/1907123/