You are given a 0-indexed binary string s
which represents the types of buildings along a street where:
-
s[i] = '0'
denotes that theith
building is an office and -
s[i] = '1'
denotes that theith
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 the1st
,3rd
, and5th
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
Top comments (0)