Skip to main content
Talentd

Number of Ways to Select Buildings - Solution & Explanation

MediumStringDynamic ProgrammingPrefix Sum14 min readAsked at: Amazon, De Shaw, Dream11
Practice this problem

Problem Statement

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 and
  • s[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.

  • For example, given 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 <= 105
  • s[i] is either '0' or '1'.

Approach Overview

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.

Approach 1: Approach 1: Two-Pointer Technique

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Hash Map Technique

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n). Space Complexity: O(n), for storing elements and keys.

Try this approach in the editor →

Approach 3: Counting + Enumeration

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two-Pointer / Prefix CountingO(n)O(1)Best general solution. Efficient when scanning a binary string and counting subsequences centered at each index.
Hash Map TechniqueO(n)O(n)Useful when modeling subsequence construction with incremental states or when extending to more complex pattern tracking.

Video Solution

2222. Number of Ways to Select Buildings || Leetcode BiWeekly Contest 75 || Leetcode 2222 • Bro Coders • 4,201 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Ways to Select Buildings easy or hard?
The problem is rated Medium on LeetCode. The main difficulty is recognizing that each building can serve as the center of a valid subsequence and that prefix counts allow computing combinations in constant time per index.
Number of Ways to Select Buildings Python/Java solution
Most implementations follow the same logic: track left zeros and ones, compute right counts dynamically, and add combinations for each position. The algorithm is easily implemented in Python, Java, C++, C#, and JavaScript with a single linear pass.
How to solve Number of Ways to Select Buildings in O(n)?
First count total zeros and ones. Then iterate through the string while maintaining counts of characters on the left. For each index, treat it as the middle building and multiply left counts with remaining right counts to form 010 or 101 patterns.
What is the best approach for Number of Ways to Select Buildings?
The optimal approach uses prefix counting with a two-pointer style scan. Treat each building as the middle of a triplet and count how many opposite-type buildings exist on the left and right. This allows counting 010 and 101 patterns in O(n) time with O(1) space.
Is Number of Ways to Select Buildings asked at Google/Amazon/Meta?
Subsequence counting problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The problem tests understanding of prefix counts, combinatorics, and linear-time optimization.
What data structure is used in Number of Ways to Select Buildings?
The most common solution uses simple integer counters for prefix frequencies. Alternative implementations may use hash maps to track character counts and pair states while building subsequences.
What is the time complexity of Number of Ways to Select Buildings?
The optimal solution runs in O(n) time because the string is scanned once while maintaining prefix counts of zeros and ones. Space complexity is O(1) since only a few counters are required.

Ready to solve this problem?

Practice Number of Ways to Select Buildings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring