Number of Ways to Select Buildings - Video Solutions

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.