## DEV Community

Abhishek Chaudhary

Posted on

# Number of Ways to Select Buildings

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 = "0**0**1**1**0**1**"`, we cannot select the `1st`, `3rd`, and `5th` buildings as that would form `"0**11**"` 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 "00*110*1" forms "010"
• [0,3,4] from "001*10*1" forms "010"
• [1,2,4] from "0*0110*1" forms "010"
• [1,3,4] from "0*0110*1" forms "010"
• [2,4,5] from "00*1101*" forms "101"
• [3,4,5] from "001*101*" 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 <= 105`
• `s[i]` is either `'0'` or `'1'`.

SOLUTION:

``````class Solution:
def numberOfWays(self, s: str) -> int:
n = len(s)
z = 0
o = 0
zeroes = [z]
ones = [o]
for c in s:
if c == '0':
z += 1
if c == '1':
o += 1
zeroes.append(z)
ones.append(o)
ways = 0
for i in range(n):
if s[i] == '0':
ways += (ones[i] - ones[0]) * (ones[-1] - ones[i + 1])
elif s[i] == '1':
ways += (zeroes[i] - zeroes[0]) * (zeroes[-1] - zeroes[i + 1])
return ways
``````