You are given a 0-indexed binary string s which represents the types of buildings along a street where:
s[i] = '0' denotes that the ith building is an office ands[i] = '1' denotes that the ith building 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.
s = "001101", we cannot select the 1st, 3rd, and 5th buildings 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'.In #2222 Number of Ways to Select Buildings, you are given a binary string representing building types. The goal is to count the number of ways to pick three buildings that form either the pattern 010 or 101, ensuring no two adjacent selections have the same type.
A common approach uses prefix counts of zeros and ones. For each index treated as the middle building, calculate how many valid buildings exist on the left and right sides. If the middle building is '0', you need a '1' on both sides to form 101. If it is '1', you need '0' on both sides to form 010. Multiplying the counts of valid left and right options gives the number of combinations for that position.
This strategy can be implemented using prefix sums or running counters, resulting in an efficient O(n) time traversal with O(1) or O(n) auxiliary space depending on the implementation.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Prefix Sum Counting | O(n) | O(n) |
| Optimized Running Counters | O(n) | O(1) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
There are only 2 valid patterns: ‘101’ and ‘010’. Think about how we can construct these 2 patterns from smaller patterns.
Count the number of subsequences of the form ‘01’ or ‘10’ first. Let n01[i] be the number of ‘01’ subsequences that exist in the prefix of s up to the ith building. How can you compute n01[i]?
Let n0[i] and n1[i] be the number of ‘0’s and ‘1’s that exists in the prefix of s up to i respectively. Then n01[i] = n01[i – 1] if s[i] == ‘0’, otherwise n01[i] = n01[i – 1] + n0[i – 1].
The same logic applies to building the n10 array and subsequently the n101 and n010 arrays for the number of ‘101’ and ‘010‘ subsequences.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this type of pattern-counting problem appears in coding interviews at large tech companies. It tests understanding of prefix sums, counting techniques, and efficient single-pass algorithms.
Prefix sum arrays or simple running counters are the most effective tools. They allow you to quickly know how many zeros or ones appear before and after a given index without repeated scanning.
The optimal approach scans the string once while maintaining counts of zeros and ones on the left and right. For each building treated as the middle element, you calculate valid combinations using prefix counts. This allows the problem to be solved in O(n) time.
Yes. Instead of storing full prefix arrays, you can maintain running counts of zeros and ones on the left while precomputing totals for the right side. This reduces the space complexity to O(1).