Number of Ways to Select Buildings

#leetcode #dsa #theabbie

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