2222. Number of Ways to Select Buildings
Description
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 ands[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 = "001101"
, we cannot select the1st
,3rd
, and5th
buildings as that would form"011"
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 <= 105
s[i]
is either'0'
or'1'
.
Solutions
Solution 1: Counting + Enumeration
According to the problem description, we need to choose $3$ buildings, and two adjacent buildings cannot be of the same type.
We can enumerate the middle building, assuming it is $x$, then the types of buildings on the left and right sides can only be $x \oplus 1$, where $\oplus$ denotes the XOR operation. Therefore, we can use two arrays $l$ and $r$ to record the number of building types on the left and right sides, respectively. Then, we enumerate the middle building and calculate the answer.
The time complexity is $O(n)$, where $n$ is the length of the string $s$. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|