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'.Problem Overview: You receive a binary string where 0 represents an office and 1 represents a restaurant. The task is to count the number of ways to choose three buildings such that no two consecutive chosen buildings have the same type. Valid patterns are therefore 010 and 101. The challenge is counting these subsequences efficiently without checking every possible triple.
Approach 1: Two-Pointer Technique (O(n) time, O(1) space)
This approach scans the string once while tracking how many 0s and 1s appear on the left and right of the current position. Treat the current building as the middle of the triplet. If the current value is 0, valid patterns are 1-0-1, so multiply the number of 1s seen on the left with the number of 1s remaining on the right. If the current value is 1, count 0-1-0 combinations using the same idea. The algorithm first counts total zeros and ones, then iterates through the string updating left counts while decreasing right counts. Each index contributes directly to the answer through simple arithmetic. This method works because every valid subsequence must have a middle building, so counting possibilities around that middle avoids generating all combinations.
Approach 2: Hash Map Technique (O(n) time, O(n) space)
This method counts valid subsequences by building frequency maps for prefixes and tracking pair patterns. As you iterate through the string, maintain a hash map storing how many times each character (0 or 1) has appeared so far. Another structure tracks counts of two‑character patterns like 01 and 10. When processing the next character, extend previously formed pairs to create valid triplets (010 or 101). Hash lookups provide constant‑time updates while accumulating the total number of valid selections. This approach mirrors a small dynamic programming state machine where each character extends earlier states.
The idea closely relates to counting subsequences in string problems and incremental state tracking used in dynamic programming. The prefix counting pattern also appears in many problems that rely on prefix sums or prefix frequencies.
Recommended for interviews: The two-pointer prefix counting method is the expected solution. It runs in linear time with constant space and clearly demonstrates understanding of subsequence counting. The hash map approach still achieves O(n) time but introduces extra memory and more moving parts. In interviews, showing the brute reasoning (counting triplets) and then optimizing to the prefix-based linear solution signals strong algorithmic thinking.
This approach involves using two pointers to traverse the data. One pointer starts at the beginning and the other at the end. Depending on the condition, move one or both of the pointers closer together. This technique is useful for problems that involve searching or manipulating data in a linear fashion.
This C function utilizes the two-pointer technique. By incrementally adjusting the pointers based on a condition (which would be problem-specific), you can effectively process or analyze the data. This template is flexible and must be adapted depending on the specific algorithm.
Time Complexity: O(n), where n is the number of elements in the array. Space Complexity: O(1); no additional space is used apart from variables.
This approach involves using a hash map (or dictionary) to keep track of elements that have been encountered so far. It is particularly effective in cases where you need quick lookups for some already processed data, such as finding complements or duplicate elements in linear time.
The C implementation involves a basic structure to hold key-value pairs, alongside a simple hash function. While C does not have a built-in hash map, you can simulate it using structs and arrays tailored to specific problems.
Time Complexity: O(n). Space Complexity: O(n), for storing elements and keys.
According to the problem description, we need to choose 3 buildings, and two adjacent buildings cannot be of the same type.
We can enumerate the middle building, assuming it is x, then the types of buildings on the left and right sides can only be x \oplus 1, where \oplus denotes the XOR operation. Therefore, we can use two arrays l and r to record the number of building types on the left and right sides, respectively. Then, we enumerate the middle building and calculate the answer.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Two-Pointer Technique | Time Complexity: O(n), where n is the number of elements in the array. Space Complexity: O(1); no additional space is used apart from variables. |
| Approach 2: Hash Map Technique | Time Complexity: O(n). Space Complexity: O(n), for storing elements and keys. |
| Counting + Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer / Prefix Counting | O(n) | O(1) | Best general solution. Efficient when scanning a binary string and counting subsequences centered at each index. |
| Hash Map Technique | O(n) | O(n) | Useful when modeling subsequence construction with incremental states or when extending to more complex pattern tracking. |
2222. Number of Ways to Select Buildings || Leetcode BiWeekly Contest 75 || Leetcode 2222 • Bro Coders • 4,140 views views
Watch 9 more video solutions →Practice Number of Ways to Select Buildings with our built-in code editor and test cases.
Practice on FleetCode