Number of Ways to Select Buildings - Practice Coding Problems

Number of Ways to Select Buildings - Problem

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

Input & Output

Example 1 — Basic Case

$ Input: s = "001101"

› Output: 3

💡 Note: Valid selections: indices (0,2,4) forming "010", indices (0,2,5) forming "010", and indices (1,2,4) forming "010". All three are alternating patterns.

Example 2 — All Same Type

$ Input: s = "11111"

› Output: 0

💡 Note: No valid selections possible since all buildings are restaurants (type 1), so any selection would have consecutive buildings of the same type.

Example 3 — Minimum Length

$ Input: s = "010"

› Output: 1

💡 Note: Only one way to select 3 buildings from 3 total: indices (0,1,2) forming "010" which is a valid alternating pattern.

Constraints

3 ≤ s.length ≤ 10⁵
s[i] is either '0' or '1'

Visualization

Tap to expand

Understanding the Visualization

Input String

Binary string representing building types (0=office, 1=restaurant)

Valid Patterns

Find all subsequences of length 3 with alternating types

Count Result

Total number of valid 010 and 101 patterns

Key Takeaway

🎯 Key Insight: Only patterns 010 and 101 are valid - count them efficiently using dynamic programming

Asked in

G Google 15 a Amazon 12 M Microsoft 8

Brief HTML summary: The key insight is that only two valid patterns exist: 010 and 101. Best approach uses dynamic programming to count these patterns in a single pass. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Triplets	O(n³)	O(1)	Check every possible combination of 3 buildings
Prefix Sum Optimization	O(n²)	O(1)	Count valid patterns using prefix sums for each position
Dynamic Programming - Single Pass	O(n)	O(1)	Count valid patterns in one pass using running counts

Brute Force - Check All Triplets — Algorithm Steps

Step 1: Generate all possible triplets (i,j,k) where i < j < k
Step 2: For each triplet, check if s[i], s[j], s[k] form pattern 010 or 101
Step 3: Count valid patterns

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Triplets

Try all combinations (i,j,k) where i < j < k

Check Pattern

Verify if s[i]s[j]s[k] is alternating

Count Valid

Count patterns 010 and 101

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int solution(char* s) {
    int n = strlen(s);
    int count = 0;
    
    // Check all possible triplets
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                // Check if pattern is alternating (010 or 101)
                if (s[i] != s[j] && s[j] != s[k]) {
                    count++;
                }
            }
        }
    }
    
    return count;
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;  // Remove newline
    
    int result = solution(s);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops to check all possible triplets

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

23.5K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Triplets — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler