Solution Explanation: Number of Ways to Select Buildings

This problem asks us to find the number of ways to select three buildings from a street such that no two consecutive buildings are of the same type. The buildings are represented by a binary string, where '0' denotes an office and '1' denotes a restaurant.

Approach:

The most efficient approach uses a linear scan with prefix sums. Instead of brute-force enumeration of all possible triplets, we utilize the following observation:

• Focus on the middle building: Once we select a middle building, the building to its left and right must be of a different type.

The algorithm works as follows:

1. Initialization: We create two arrays, l and r. l[i] keeps track of the count of buildings of type i to the left of the currently considered building, and r[i] keeps track of the count of buildings of type i to the right. Initially, r is populated with the total counts of '0's and '1's in the string.

2. Iteration: We iterate through the input string s. For each building at index i:

   • We decrement the count of the current building's type in r.
   • We calculate the number of valid selections where the current building is the middle building: This is given by l[x ^ 1] * r[x ^ 1], where x is the type of the current building (0 or 1), and x ^ 1 represents the opposite type. The product represents all possible combinations of left and right buildings that satisfy the condition.
   • We increment the count of the current building's type in l.

3. Return: After iterating through all buildings, the accumulated ans will be the total number of valid selections.

Time Complexity: O(n), where n is the length of the string. We iterate through the string once.

Space Complexity: O(1). We use a constant amount of extra space for the l and r arrays.

Code (Python):

class Solution:
    def numberOfWays(self, s: str) -> int:
        l = [0, 0]  # Count of 0s and 1s to the left
        r = [s.count('0'), s.count('1')]  # Count of 0s and 1s to the right
        ans = 0
        for x in map(int, s):  # Iterate through the string (converting chars to ints)
            r[x] -= 1
            ans += l[x ^ 1] * r[x ^ 1]
            l[x] += 1
        return ans

Code (Java):

class Solution {
    public long numberOfWays(String s) {
        int[] l = new int[2];
        int[] r = new int[2];
        for (char c : s.toCharArray()) {
            r[c - '0']++;
        }
        long ans = 0;
        for (char c : s.toCharArray()) {
            int x = c - '0';
            r[x]--;
            ans += (long)l[x ^ 1] * r[x ^ 1];
            l[x]++;
        }
        return ans;
    }
}

The other languages (C++, Go, TypeScript) follow a very similar structure, adapting the syntax to the respective language. The core logic remains the same efficient linear scan using prefix-sum-like counting.