LeetCode-in-Java
2222. Number of Ways to Select Buildings
Medium
You are given a 0-indexed binary string s which represents the types of buildings along a street where:
s[i] = '0'denotes that theithbuilding is an office ands[i] = '1'denotes that theithbuilding 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, and5thbuildings 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 “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 <= 105s[i]is either'0'or'1'.
Solution
public class Solution {
public long numberOfWays(String s) {
long z = 0;
long o = 0;
long zo = 0;
long oz = 0;
long zoz = 0;
long ozo = 0;
for (char c : s.toCharArray()) {
if (c == '0') {
zoz += zo;
oz += o;
z++;
} else {
ozo += oz;
zo += z;
o++;
}
}
return zoz + ozo;
}
}