Number of Ways to Select Buildings

Medium
877.

Number of Ways to Select Buildings

Number of Ways to Select Buildings is a medium coding problem on strings, dynamic programming and prefix sum, asked in Amazon, Google, Zoho and Dream11 interviews.

s[i] is '0' for an office and '1' for a restaurant. You must pick three buildings, in order of position, so that no two consecutive picks are the same type — that is, the picked pattern is "010" or "101".

Return the number of valid selections.

Example 1

Input
s = "001101"
Output
6

Example 2

Input
s = "11100"
Output
0
Explanation
No valid alternating triple exists.

Example 3

Input
s = "0101"
Output
2
Explanation
"010" using positions 0,1,2 and "101" using 1,2,3.

Constraints

  • 3 <= s.length <= 1500
  • s[i] is '0' or '1'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var numberOfWays = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Ways to Select Buildings — Problem & Solution

Number of Ways to Select Buildings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Number of Ways to Select Buildings is a medium coding problem on strings, dynamic programming and prefix sum, asked in Amazon, Google, Zoho and Dream11 interviews.

Problem statement

s[i] is '0' for an office and '1' for a restaurant. You must pick three buildings, in order of position, so that no two consecutive picks are the same type — that is, the picked pattern is "010" or "101".

Return the number of valid selections.

Example 1

Input: s = "001101"
Output: 6

Example 2

Input: s = "11100"
Output: 0
Explanation: No valid alternating triple exists.

Example 3

Input: s = "0101"
Output: 2
Explanation: "010" using positions 0,1,2 and "101" using 1,2,3.

Constraints

  • 3 <= s.length <= 1500
  • s[i] is '0' or '1'

Hints for Number of Ways to Select Buildings

  1. Hint 1

    Enumerate by the middle building — the two ends are then forced to be the other type.

  2. Hint 2

    For a middle '1' at index i, the count is (zeros before i) × (zeros after i).

  3. Hint 3

    Keep running prefix counts of each type as you sweep.

How to solve Number of Ways to Select Buildings

Fix the middle pick. The pattern must alternate, so the two outer picks are both the opposite type, and they are chosen independently from the prefix and the suffix — a simple product.

Approach

  1. Count the total zeros and ones.
  2. Sweep, keeping z and o, the counts strictly before the current index.
  3. At a '1', add z · (totalZeros - z); at a '0', add o · (totalOnes - o).

Why it works

Every valid triple has exactly one middle element, so classifying by it counts each triple once. Given the middle, the left pick is any opposite-type building before it and the right pick any opposite-type building after it, and those choices are independent — hence the product.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Enumerating triples directly is O(n³).
  • The running counts must exclude the current index, which is why they are updated after the contribution.
  • The total reaches about 5 · 10^8 at the stated size.

Reference solution

Python

def numberOfWays(s: str) -> int:
    total_zeros = s.count("0")
    total_ones = len(s) - total_zeros
    res = z = o = 0
    for ch in s:
        if ch == "0":
            res += o * (total_ones - o)
            z += 1
        else:
            res += z * (total_zeros - z)
            o += 1
    return res

Java

public static int numberOfWays(String s) {
    long totalZeros = 0, totalOnes = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '0') totalZeros++; else totalOnes++;
    }
    long res = 0, z = 0, o = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '0') {
            res += o * (totalOnes - o);
            z++;
        } else {
            res += z * (totalZeros - z);
            o++;
        }
    }
    return (int) res;
}

C++

int numberOfWays(string s) {
    long long totalZeros = 0, totalOnes = 0;
    for (char ch : s) {
        if (ch == '0') totalZeros++; else totalOnes++;
    }
    long long res = 0, z = 0, o = 0;
    for (char ch : s) {
        if (ch == '0') {
            res += o * (totalOnes - o);
            z++;
        } else {
            res += z * (totalZeros - z);
            o++;
        }
    }
    return (int) res;
}

JavaScript

var numberOfWays = function(s) {
    var totalZeros = 0, totalOnes = 0, i;
    for (i = 0; i < s.length; i++) {
        if (s.charAt(i) === "0") totalZeros++; else totalOnes++;
    }
    var res = 0, z = 0, o = 0;
    for (i = 0; i < s.length; i++) {
        if (s.charAt(i) === "0") { res += o * (totalOnes - o); z++; }
        else { res += z * (totalZeros - z); o++; }
    }
    return res;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming