Number of Ways to Select Buildings

You are given a binary string s of length N, where s[i] = '0' represents an office and s[i] = '1' represents a restaurant.

Your task is to find the number of ways to select three buildings at indices i, j, and k such that i < j < k, and the types of the selected buildings are alternating. This means the selected sequence of building types must be either "010" or "101".

Input Format:

A single line containing the binary string s.

Output Format:

Print a single integer representing the total number of valid ways to select three buildings.

Note:

A brute-force approach of checking every possible combination of three indices would be O(N^3), which is too slow for the given constraints.
The problem can be solved efficiently in O(N) time. The key is to iterate through each possible middle building j.
  If s[j] is '1', we need to form a "010" triplet. The number of ways to do this is (number of '0's to the left of j) * (number of '0's to the right of j).
  If s[j] is '0', we need to form a "101" triplet. The number of ways to do this is (number of '1's to the left of j) * (number of '1's to the right of j).
These "counts to the left" and "counts to the right" can be pre-calculated or tracked in a single pass.