2222. Number of Ways to Select Buildings Medium

1/**
2 * [2222] Number of Ways to Select Buildings
3 *
4 * You are given a 0-indexed binary string s which represents the types of buildings along a street where:
5 *
6 * s[i] = '0' denotes that the i^th building is an office and
7 * s[i] = '1' denotes that the i^th building is a restaurant.
8 *
9 * 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.
10 *
11 * For example, given s = "0<u>0</u>1<u>1</u>0<u>1</u>", we cannot select the 1^st, 3^rd, and 5^th buildings as that would form "0<u>11</u>" which is not allowed due to having two consecutive buildings of the same type.
12 *
13 * Return the number of valid ways to select 3 buildings.
14 *  
15 * Example 1:
16 *
17 * Input: s = "001101"
18 * Output: 6
19 * Explanation:
20 * The following sets of indices selected are valid:
21 * - [0,2,4] from "<u>0</u>0<u>1</u>1<u>0</u>1" forms "010"
22 * - [0,3,4] from "<u>0</u>01<u>10</u>1" forms "010"
23 * - [1,2,4] from "0<u>01</u>1<u>0</u>1" forms "010"
24 * - [1,3,4] from "0<u>0</u>1<u>10</u>1" forms "010"
25 * - [2,4,5] from "00<u>1</u>1<u>01</u>" forms "101"
26 * - [3,4,5] from "001<u>101</u>" forms "101"
27 * No other selection is valid. Thus, there are 6 total ways.
28 *
29 * Example 2:
30 *
31 * Input: s = "11100"
32 * Output: 0
33 * Explanation: It can be shown that there are no valid selections.
34 *
35 *  
36 * Constraints:
37 *
38 * 3 <= s.length <= 10^5
39 * s[i] is either '0' or '1'.
40 *
41 */
42pub struct Solution {}
43
44// problem: https://leetcode.com/problems/number-of-ways-to-select-buildings/
45// discuss: https://leetcode.com/problems/number-of-ways-to-select-buildings/discuss/?currentPage=1&orderBy=most_votes&query=
46
47// submission codes start here
48
49impl Solution {
50    pub fn number_of_ways(s: String) -> i64 {
51        let (mut one, mut zero, mut one_zero, mut zero_one, mut result) = (0, 0, 0, 0, 0);
52        for i in s.chars() {
53            if i == '0' {
54                zero += 1;
55                one_zero += one;
56                result += zero_one;
57            } else {
58                one += 1;
59                zero_one += zero;
60                result += one_zero;
61            }
62        }
63
64        result
65    }
66}
67
68// submission codes end
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73
74    #[test]
75    fn test_2222() {
76        assert_eq!(Solution::number_of_ways("001101".to_string()), 6);
77    }
78}
79