You are given a **0-indexed** binary string `s`

which represents the types of buildings along a street where:

`s[i] = '0'`

denotes that the`i`

building is an office and^{th}`s[i] = '1'`

denotes that the`i`

building is a restaurant.^{th}

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`

, we cannot select the1**0**0**1**"**1**`1`

,^{st}`3`

, and^{rd}`5`

buildings as that would form^{th}`"0`

which is"__11__**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:6Explanation:The following sets of indices selected are valid: - [0,2,4] from "00111" forms "010" - [0,3,4] from "0001101" 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:0Explanation:It can be shown that there are no valid selections.

**Constraints:**

`3 <= s.length <= 10`

^{5}`s[i]`

is either`'0'`

or`'1'`

.

**Solution: DP**

The brute force solution will take O(n^{3}) which will lead to TLE.

Since the only two valid cases are “010” and “101”.

We just need to count how many 0s and 1s, thus we can count 01s and 10s and finally 010s and 101s.

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: long long numberOfWays(string s) { long long c0 = 0, c1 = 0, c01 = 0, c10 = 0, c101 = 0, c010 = 0; for (char c : s) { if (c == '0') { ++c0; c10 += c1; c010 += c01; } else { ++c1; c01 += c0; c101 += c10; } } return c101 + c010; } }; |