#2222
Number of Ways to Select Buildings
specialist · 855 · lc medium +31 · verified · 50.9% accepted · 1,059 likes · top 39%
Description
You are given a 0-indexed binary string s representing building types along a street:
- s[i] = '0' indicates an office at position i.
- s[i] = '1' indicates a restaurant at position i.
You want to choose exactly 3 buildings for inspection such that no two adjacent selections share the same type.
- For example, from s = "001101", the selection at indices 1, 3, and 5 yields "011" which is invalid because two consecutive selections are the same type.
Return the total count of valid 3-building selections.
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.
Code
1
2
3