You are given a binary string s indexed from $0$, where each character represents the type of building along a street:

• s[i] = '0' denotes that the $i^{ ext{th}}$ building is an office.

• s[i] = '1' denotes that the $i^{ ext{th}}$ building is a restaurant.

You want to select $3$ buildings such that no two consecutive chosen buildings are of the same type. That is, you must choose three indices $i$, $j$, and $k$ with $0 \leq i < j < k <$ s.length such that the selected sequence of characters forms either '010' or '101'.

Return the total number of valid ways to select $3$ buildings.

Constraints:

• $3 \leq$ s.length $\leq 10^5$

• s[i] is either '0' or '1'.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.