Number of Ways to Select Buildings

A single line containing the binary string s.

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

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.

Sample Input 1:

001101

Sample Output 1:

6

Explanation for Sample 1:

We iterate through each possible middle building:
Index 2 (s[2]='1'): Needs "010". There are two '0's to its left (at indices 0, 1) and one '0' to its right (at index 4). Ways = 2 * 1 = 2.
Index 3 (s[3]='1'): Needs "010". There are two '0's to its left and one '0' to its right. Ways = 2 * 1 = 2.
Index 4 (s[4]='0'): Needs "101". There are two '1's to its left (at indices 2, 3) and one '1' to its right (at index 5). Ways = 2 * 1 = 2.
Total ways = 2 + 2 + 2 = 6.

Sample Input 2:

11100

Sample Output 2:

0

Explanation for Sample 2:

Middle building cannot be the first or last.
If middle is '1' (index 1 or 2), there are no '0's to its left to form a "010" sequence.
If middle is '0' (index 3), there are no '1's to its right to form a "101" sequence.
No valid triplets can be formed.

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

3 <= N <= 10^5
`s[i]` is either '0' or '1'.

Time limit: 1 sec