Scale Engineer

Number of Ways to Select Buildings

Med
#2025Time: O(N³) - Where N is the length of the string `s`. The three nested loops lead to a cubic number of iterations, making this approach very slow.Space: O(1) - We only use a few variables to store loop indices and the final count, regardless of the input size.1 company
Patterns
Dynamic ProgrammingPrefix Sum
Data structures
String
Companies
Dream11

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

The most straightforward solution is to check every possible combination of three buildings. We can use three nested loops to select three distinct indices i, j, and k such that i < j < k. For each triplet of indices, we examine the corresponding building types s[i], s[j], and s[k]. If they form an alternating pattern, i.e., "010" or "101", we increment our count of valid selections.

Algorithm

  1. Initialize a long counter ways to 0.
  2. Get the length of the string, n.
  3. Use three nested loops to select three distinct indices i, j, and k such that 0 <= i < j < k < n.
    • The outer loop for i runs from 0 to n-3.
    • The middle loop for j runs from i+1 to n-2.
    • The inner loop for k runs from j+1 to n-1.
  4. Inside the innermost loop, check if the selected buildings form a valid alternating pattern:
    • Check if s.charAt(i) != s.charAt(j) and s.charAt(j) != s.charAt(k).
    • If the condition is true, it means we have a valid "010" or "101" pattern. Increment ways.
  5. After all loops complete, return ways.

Walkthrough

This method systematically generates all triplets of indices (i, j, k) in increasing order. For each triplet, it performs a simple check on the characters at these positions in the input string s. A valid selection requires that the type of the first building is different from the second, and the second is different from the third. This single check s.charAt(i) != s.charAt(j) && s.charAt(j) != s.charAt(k) correctly identifies both "010" and "101" patterns.

class Solution {    public long numberOfWays(String s) {        long ways = 0;        int n = s.length();        for (int i = 0; i < n; i++) {            for (int j = i + 1; j < n; j++) {                for (int k = j + 1; k < n; k++) {                    if (s.charAt(i) != s.charAt(j) && s.charAt(j) != s.charAt(k)) {                        ways++;                    }                }            }        }        return ways;    }}

Complexity

Time

O(N³) - Where N is the length of the string `s`. The three nested loops lead to a cubic number of iterations, making this approach very slow.

Space

O(1) - We only use a few variables to store loop indices and the final count, regardless of the input size.

Trade-offs

Pros

  • Simple to understand and implement.

  • Correctly solves the problem for small input sizes.

Cons

  • Extremely inefficient due to its cubic time complexity.

  • Will result in a 'Time Limit Exceeded' error for the given constraints (n up to 10^5).

Solutions

class Solution {public  long numberOfWays(String s) {    int n = s.length();    int cnt0 = 0;    for (char c : s.toCharArray()) {      if (c == '0') {        ++cnt0;      }    }    int cnt1 = n - cnt0;    long ans = 0;    int c0 = 0, c1 = 0;    for (char c : s.toCharArray()) {      if (c == '0') {        ans += c1 * (cnt1 - c1);        ++c0;      } else {        ans += c0 * (cnt0 - c0);        ++c1;      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem