2222. Number of Ways to Select Buildings LeetCode Solution

In this guide, you will get 2222. Number of Ways to Select Buildings LeetCode Solution with the best time and space complexity. The solution to Number of Ways to Select Buildings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Number of Ways to Select Buildings solution in C++
Number of Ways to Select Buildings solution in Java
Number of Ways to Select Buildings solution in Python
Additional Resources

2222. Number of Ways to Select Buildings LeetCode Solution image

Problem Statement of Number of Ways to Select Buildings

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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

2222. Number of Ways to Select Buildings LeetCode Solution in C++

class Solution {
 public:
  long long numberOfWays(string s) {
    long ans = 0;
    // before[i] := the number of i before the current digit
    vector<int> before(2);
    // after[i] := the number of i after the current digit
    vector<int> after(2);
    after[0] = ranges::count(s, '0');
    after[1] = s.length() - after[0];

    for (const char c : s) {
      const int num = c - '0';
      --after[num];
      if (num == 0)
        ans += before[1] * after[1];
      else
        ans += before[0] * after[0];
      ++before[num];
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

2222. Number of Ways to Select Buildings LeetCode Solution in Java

class Solution {
  public long numberOfWays(String s) {
    long ans = 0;
    // before[i] := the number of i before the current digit
    int[] before = new int[2];
    // after[i] := the number of i after the current digit
    int[] after = new int[2];
    after[0] = (int) s.chars().filter(c -> c == '0').count();
    after[1] = s.length() - after[0];

    for (final char c : s.toCharArray()) {
      final int num = c - '0';
      --after[num];
      if (num == 0)
        ans += before[1] * after[1];
      else
        ans += before[0] * after[0];
      ++before[num];
    }

    return ans;
  }
}
// code provided by PROGIEZ

2222. Number of Ways to Select Buildings LeetCode Solution in Python

class Solution:
  def numberOfWays(self, s: str) -> int:
    ans = 0
    # before[i] := the number of i before the current digit
    before = [0] * 2
    # after[i] := the number of i after the current digit
    after = [0] * 2
    after[0] = s.count('0')
    after[1] = len(s) - after[0]

    for c in s:
      num = int(c)
      after[num] -= 1
      if num == 0:
        ans += before[1] * after[1]
      else:
        ans += before[0] * after[0]
      before[num] += 1

    return ans
 # code by PROGIEZ