Get started

Number of Ways to Select Buildings — Medium Problem & Solution

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…

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'

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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue