# Number of Ways to Select Buildings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-ways-to-select-buildings)
Canonical: https://scaleengineer.com/dsa/problems/number-of-ways-to-select-buildings
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** String
**Companies:** [Dream11](https://scaleengineer.com/companies/dream11)
---
## Problem
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.

* For example, given `s = "0**0**1**1**0**1**"`, we cannot select the `1st`, `3rd`, and `5th` buildings as that would form `"0**11**"` which is **not** allowed due to having two consecutive buildings of the same type.

Return _the **number of valid ways** to select 3 buildings._

**Example 1:**

**Input:** s = "001101"
**Output:** 6
**Explanation:** 
The following sets of indices selected are valid:
- [0,2,4] from "**0**0**1**1**0**1" forms "010"
- [0,3,4] from "**0**01**10**1" forms "010"
- [1,2,4] from "0**01**1**0**1" forms "010"
- [1,3,4] from "0**0**1**10**1" forms "010"
- [2,4,5] from "00**1**1**01**" forms "101"
- [3,4,5] from "001**101**" forms "101"
No other selection is valid. Thus, there are 6 total ways.

**Example 2:**

**Input:** s = "11100"
**Output:** 0
**Explanation:** It can be shown that there are no valid selections.

**Constraints:**

* `3 <= s.length <= 105`
* `s[i]` is either `'0'` or `'1'`.

# Approaches
## Brute Force with Triple Loop
The most straightforward solution is to check every possible combination of three buildings. We can use three nested loops to select three distinct indices `i`, `j`, and `k` such that `i < j < k`. For each triplet of indices, we examine the corresponding building types `s[i]`, `s[j]`, and `s[k]`. If they form an alternating pattern, i.e., `"010"` or `"101"`, we increment our count of valid selections.
**Time:** O(N³) - Where N is the length of the string `s`. The three nested loops lead to a cubic number of iterations, making this approach very slow. · **Space:** O(1) - We only use a few variables to store loop indices and the final count, regardless of the input size.
**Pros:** Simple to understand and implement.; Correctly solves the problem for small input sizes.
**Cons:** Extremely inefficient due to its cubic time complexity.; Will result in a 'Time Limit Exceeded' error for the given constraints (`n` up to 10^5).
### Explanation
This method systematically generates all triplets of indices `(i, j, k)` in increasing order. For each triplet, it performs a simple check on the characters at these positions in the input string `s`. A valid selection requires that the type of the first building is different from the second, and the second is different from the third. This single check `s.charAt(i) != s.charAt(j) && s.charAt(j) != s.charAt(k)` correctly identifies both `"010"` and `"101"` patterns.

```java
class Solution {
    public long numberOfWays(String s) {
        long ways = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (s.charAt(i) != s.charAt(j) && s.charAt(j) != s.charAt(k)) {
                        ways++;
                    }
                }
            }
        }
        return ways;
    }
}
```
### Algorithm
1. Initialize a `long` counter `ways` to 0.
2. Get the length of the string, `n`.
3. Use three nested loops to select three distinct indices `i`, `j`, and `k` such that `0 <= i < j < k < n`.
   - The outer loop for `i` runs from `0` to `n-3`.
   - The middle loop for `j` runs from `i+1` to `n-2`.
   - The inner loop for `k` runs from `j+1` to `n-1`.
4. Inside the innermost loop, check if the selected buildings form a valid alternating pattern:
   - Check if `s.charAt(i) != s.charAt(j)` and `s.charAt(j) != s.charAt(k)`.
   - If the condition is true, it means we have a valid `"010"` or `"101"` pattern. Increment `ways`.
5. After all loops complete, return `ways`.

## Fixing the Middle Element
We can improve upon the brute-force approach by changing our perspective. Instead of picking three buildings at once, we can iterate through the string and consider each building at index `j` as the *middle* building of our selection. For each potential middle building, we then count how many valid first buildings exist to its left and how many valid third buildings exist to its right. The total number of ways for a fixed middle building is the product of these counts.
**Time:** O(N²) - For each of the N elements considered as the middle, we iterate through its left and right sides, which takes O(N) time. This results in a quadratic time complexity. · **Space:** O(1) - Constant extra space is used for counters.
**Pros:** A significant improvement over the O(N³) brute-force approach.; The logic is a good stepping stone towards the optimal solution.
**Cons:** Still inefficient for the given constraints.; Will likely result in a 'Time Limit Exceeded' error as N can be up to 10^5.
### Explanation
For each building `s[j]`, we need to find a building `s[i]` to its left (`i < j`) and a building `s[k]` to its right (`k > j`) that form a valid pattern.
- If `s[j]` is '1', we are looking for a `"010"` pattern. The number of ways to form this is `(number of '0's before j) * (number of '0's after j)`.
- If `s[j]` is '0', we are looking for a `"101"` pattern. The number of ways is `(number of '1's before j) * (number of '1's after j)`.
We can implement this by iterating `j` from `1` to `n-2`. In each iteration, we perform two more loops: one to count buildings on the left and one for the right.

```java
class Solution {
    public long numberOfWays(String s) {
        long ways = 0;
        int n = s.length();
        for (int j = 1; j < n - 1; j++) {
            long zeros_before = 0, ones_before = 0;
            for (int i = 0; i < j; i++) {
                if (s.charAt(i) == '0') {
                    zeros_before++;
                } else {
                    ones_before++;
                }
            }

            long zeros_after = 0, ones_after = 0;
            for (int k = j + 1; k < n; k++) {
                if (s.charAt(k) == '0') {
                    zeros_after++;
                } else {
                    ones_after++;
                }
            }

            if (s.charAt(j) == '1') {
                ways += zeros_before * zeros_after;
            } else { // s.charAt(j) == '0'
                ways += ones_before * ones_after;
            }
        }
        return ways;
    }
}
```
### Algorithm
1. Initialize a `long` counter `ways` to 0.
2. Iterate through the string with an index `j` from `1` to `n-2`, considering `s[j]` as the middle building.
3. For each `j`, initialize counters: `zeros_before = 0`, `ones_before = 0`, `zeros_after = 0`, `ones_after = 0`.
4. Count the number of '0's and '1's to the left of `j` by iterating from `i = 0` to `j-1`.
5. Count the number of '0's and '1's to the right of `j` by iterating from `k = j+1` to `n-1`.
6. If `s.charAt(j)` is '1' (for a `"010"` pattern), add the product `zeros_before * zeros_after` to `ways`.
7. If `s.charAt(j)` is '0' (for a `"101"` pattern), add the product `ones_before * ones_after` to `ways`.
8. After the loop for `j` finishes, return `ways`.

## Optimal Approach: Prefix Counts
The O(N²) approach is slow because it repeatedly re-calculates the counts of buildings before and after the middle element. We can optimize this to a linear time solution by calculating these counts more efficiently. By making a single pass through the string, we can maintain a running count of the '0's and '1's seen so far. The count of elements to the right of the current position can then be derived instantly from pre-calculated total counts.
**Time:** O(N) - We make a constant number of passes (two in this implementation) through the string, making the solution linear in time. · **Space:** O(1) - We only use a few variables to store total counts and running counts, which does not depend on the input size.
**Pros:** Optimal time complexity, passing all test cases efficiently.; Optimal space complexity.; Builds logically upon the less efficient approaches.
**Cons:** Requires careful handling of `long` type for the counter to prevent potential integer overflow.
### Explanation
The core idea remains the same: iterate through each building `s[j]` and treat it as the middle one. However, we avoid the nested loops by being smarter about counting.

First, we can find the `total_zeros` and `total_ones` in the entire string. Then, we iterate through the string again from left to right. We maintain two variables, `zeros_before` and `ones_before`, which store the counts of '0's and '1's to the left of our current index `j`. When we are at index `j`, we can find the counts of '0's and '1's to the right by subtracting the `_before` counts from the total counts. This allows us to calculate the number of valid combinations for each middle element in O(1) time, leading to an overall O(N) solution.

This approach is conceptually equivalent to a Dynamic Programming solution where we keep track of the counts of subsequences of length 1 (`"0"`, `"1"`) and use them to build counts of subsequences of length 2 (`"01"`, `"10"`), and finally use those to count subsequences of length 3 (`"010"`, `"101"`).

```java
class Solution {
    public long numberOfWays(String s) {
        int n = s.length();
        long total_ones = 0;
        for (char c : s.toCharArray()) {
            if (c == '1') {
                total_ones++;
            }
        }
        long total_zeros = n - total_ones;

        long ways = 0;
        long ones_before = 0;
        long zeros_before = 0;

        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1') {
                // This '1' is the middle of a "010" pattern
                long zeros_after = total_zeros - zeros_before;
                ways += zeros_before * zeros_after;
                ones_before++;
            } else { // s.charAt(i) == '0'
                // This '0' is the middle of a "101" pattern
                long ones_after = total_ones - ones_before;
                ways += ones_before * ones_after;
                zeros_before++;
            }
        }

        return ways;
    }
}
```
### Algorithm
1. **First Pass**: Iterate through the string once to calculate `total_zeros` and `total_ones`.
2. Initialize `ways = 0L`, `zeros_before = 0`, `ones_before = 0`.
3. **Second Pass**: Iterate through the string with index `j` from `0` to `n-1`.
4. For each character `s[j]`:
   - If `s.charAt(j) == '1'` (potential middle of `"010"`):
     - The number of '0's to the right is `zeros_after = total_zeros - zeros_before`.
     - Add the product `(long)zeros_before * zeros_after` to `ways`.
   - If `s.charAt(j) == '0'` (potential middle of `"101"`):
     - The number of '1's to the right is `ones_after = total_ones - ones_before`.
     - Add the product `(long)ones_before * ones_after` to `ways`.
5. **Update Counts**: After processing the character at `j`, update the `_before` counts for the next iteration. If `s.charAt(j) == '0'`, increment `zeros_before`. Otherwise, increment `ones_before`.
6. Return `ways`.

# Solutions
### Java

```java
class Solution {
public
  long numberOfWays(String s) {
    int n = s.length();
    int cnt0 = 0;
    for (char c : s.toCharArray()) {
      if (c == '0') {
        ++cnt0;
      }
    }
    int cnt1 = n - cnt0;
    long ans = 0;
    int c0 = 0, c1 = 0;
    for (char c : s.toCharArray()) {
      if (c == '0') {
        ans += c1 * (cnt1 - c1);
        ++c0;
      } else {
        ans += c0 * (cnt0 - c0);
        ++c1;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long numberOfWays(string s) {
    int n = s.size();
    int cnt0 = 0;
    for (char &c : s)
      cnt0 += c == '0';
    int cnt1 = n - cnt0;
    int c0 = 0, c1 = 0;
    long long ans = 0;
    for (char &c : s) {
      if (c == '0') {
        ans += c1 * (cnt1 - c1);
        ++c0;
      } else {
        ans += c0 * (cnt0 - c0);
        ++c1;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numberOfWays(self, s: str) -> int: n = len(s) cnt0 = s . count("0") cnt1 = n - cnt0 c0 = c1 = 0 ans = 0 for c in s: if c == "0": ans += c1 * (cnt1 - c1) c0 += 1 else: ans += c0 * (cnt0 - c0) c1 += 1 return ans

```