Number of Ways to Select Buildings

Problem Description

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 ith building is an office and
• s[i] = '1' denotes that the ith building is a restaurant.

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.

Return the number of valid ways to select 3 buildings.

Key Insights

• A valid selection of buildings must alternate between '0' and '1'.
• We can represent valid selections as patterns of '010' or '101'.
• To efficiently count valid selections, we can use prefix sums to track the count of '0's and '1's up to each index.
• By iterating through the string, we can compute valid combinations based on the counts of buildings seen so far.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

We can solve this problem by utilizing a single pass through the string while maintaining counts of '0's and '1's to the left and right of the current index. Specifically, for each position in the string, we consider it as a middle building and calculate the number of valid combinations by multiplying the counts of buildings of the opposite type that exist on either side.

1. Initialize variables to count the total number of '0's and '1's.
2. Iterate over each character in the string:
   • For each building, if it is '0', calculate the valid combinations using the counts of '1's before it and '1's after it.
   • If it is '1', do the same using the counts of '0's.
3. Sum the valid combinations.

This approach ensures that we count all valid selections efficiently.

Code Solutions