Number of Ways to Select Buildings

mediumOA Simulation: 2 problems in 90 min each round53 stepsJava · Python · C++

Choose three buildings so no two consecutive picks have the same type: the patterns are "010" and "101". For each building as the middle, multiply the count of the opposite type on its left by the count on its right.

▶ Watch the animated trace

Traced input: s = "001101" → 6. Original problem: leetcode.com/problems/number-of-ways-to-select-buildings/

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(1)

Running counts of 0s and 1s to the left; right counts come from totals.

Key idea

A valid selection is fully determined by its middle building and its type.
Middle '0' needs a '1' on each side; middle '1' needs a '0' on each side.
Right-side counts = totals minus left counts minus the current building.

Common mistakes

The answer can exceed 2³¹; use long.
Checking all triples is O(n³).

Solution

Java

long numberOfWays(String s) {
    long total0 = 0, total1 = 0;
    for (char c : s.toCharArray()) {
        if (c == '0') total0++;
        else total1++;
    }
    long left0 = 0, left1 = 0, ways = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '0') {
            long add = left1 * (total1 - left1);
            ways += add;
            left0++;
        } else {
            long add = left0 * (total0 - left0);
            ways += add;
            left1++;
        }
    }
    return ways;
}

Python

def numberOfWays(s: str) -> int:
    total0, total1 = s.count('0'), s.count('1')
    left0 = left1 = ways = 0
    for ch in s:
        if ch == '0':
            ways += left1 * (total1 - left1)
            left0 += 1
        else:
            ways += left0 * (total0 - left0)
            left1 += 1
    return ways

C++

long long numberOfWays(string s) {
    long long total0 = count(s.begin(), s.end(), '0'), total1 = s.size() - total0;
    long long left0 = 0, left1 = 0, ways = 0;
    for (char c : s) {
        if (c == '0') {
            ways += left1 * (total1 - left1);
            left0++;
        } else {
            ways += left0 * (total0 - left0);
            left1++;
        }
    }
    return ways;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
All the same No 1 has a 0 on both sides, and no 0 has a 1 on both sides.	`s = "11100"`	`0`
Alternating 010 (0,1,2) and 101 (1,2,3).	`s = "0101"`	`2`
Too short Need three buildings.	`s = "01"`	`0`