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.
- Difficulty: Medium
- Topics: Strings, Dynamic Programming, Prefix Sum
- Asked at: Amazon, Google, Zoho, Dream11
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 1500s[i] is '0' or '1'
Hints for Number of Ways to Select Buildings
Hint 1
Enumerate by the middle building — the two ends are then forced to be the other type.
Hint 2
For a middle
'1'at indexi, the count is (zeros beforei) × (zeros afteri).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
- Count the total zeros and ones.
- Sweep, keeping
zando, the counts strictly before the current index. - At a
'1', addz · (totalZeros - z); at a'0', addo · (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^8at 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 resJava
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