Number of Ways to Select Buildings
MedPrompt
You are given a 0-indexed binary string s which represents the types of buildings along a street where:
s[i] = '0'denotes that theithbuilding is an office ands[i] = '1'denotes that theithbuilding 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 = "001101", we cannot select the1st,3rd, and5thbuildings as that would form"011"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 "001101" forms "010"
- [0,3,4] from "001101" forms "010"
- [1,2,4] from "001101" forms "010"
- [1,3,4] from "001101" forms "010"
- [2,4,5] from "001101" forms "101"
- [3,4,5] from "001101" 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 <= 105s[i]is either'0'or'1'.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a
longcounterwaysto 0. - Get the length of the string,
n. - Use three nested loops to select three distinct indices
i,j, andksuch that0 <= i < j < k < n.- The outer loop for
iruns from0ton-3. - The middle loop for
jruns fromi+1ton-2. - The inner loop for
kruns fromj+1ton-1.
- The outer loop for
- Inside the innermost loop, check if the selected buildings form a valid alternating pattern:
- Check if
s.charAt(i) != s.charAt(j)ands.charAt(j) != s.charAt(k). - If the condition is true, it means we have a valid
"010"or"101"pattern. Incrementways.
- Check if
- After all loops complete, return
ways.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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 (
nup to 10^5).
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.
Algorithm
- Initialize a
longcounterwaysto 0. - Iterate through the string with an index
jfrom1ton-2, considerings[j]as the middle building. - For each
j, initialize counters:zeros_before = 0,ones_before = 0,zeros_after = 0,ones_after = 0. - Count the number of '0's and '1's to the left of
jby iterating fromi = 0toj-1. - Count the number of '0's and '1's to the right of
jby iterating fromk = j+1ton-1. - If
s.charAt(j)is '1' (for a"010"pattern), add the productzeros_before * zeros_aftertoways. - If
s.charAt(j)is '0' (for a"101"pattern), add the productones_before * ones_aftertoways. - After the loop for
jfinishes, returnways.
Walkthrough
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 iteratingjfrom1ton-2. In each iteration, we perform two more loops: one to count buildings on the left and one for the right.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- First Pass: Iterate through the string once to calculate
total_zerosandtotal_ones. - Initialize
ways = 0L,zeros_before = 0,ones_before = 0. - Second Pass: Iterate through the string with index
jfrom0ton-1. - 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_aftertoways.
- The number of '0's to the right is
- 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_aftertoways.
- The number of '1's to the right is
- If
- Update Counts: After processing the character at
j, update the_beforecounts for the next iteration. Ifs.charAt(j) == '0', incrementzeros_before. Otherwise, incrementones_before. - Return
ways.
Walkthrough
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").
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; }}Complexity
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.
Trade-offs
Pros
Optimal time complexity, passing all test cases efficiently.
Optimal space complexity.
Builds logically upon the less efficient approaches.
Cons
Requires careful handling of
longtype for the counter to prevent potential integer overflow.
Solutions
Solution
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; }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.