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 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 = "0 _**0**_ 1 _**1**_ 0 _**1**_ ", we cannot select the 1st, 3rd, and 5th buildings as that would form "0** _11_** " which is not allowed due to having two consecutive buildings of the same type.

Return thenumber of valid ways to select 3 buildings.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Input: s = "001101"
Output: 6
Explanation: 
The following sets of indices selected are valid:
- [0,2,4] from "_**0**_ 0** _1_** 1** _0_** 1" forms "010"
- [0,3,4] from "_**0**_ 01 _**10**_ 1" forms "010"
- [1,2,4] from "0 _**01**_ 1 _**0**_ 1" forms "010"
- [1,3,4] from "0 _**0**_ 1 _**10**_ 1" forms "010"
- [2,4,5] from "00 _**1**_ 1 _**01**_ " forms "101"
- [3,4,5] from "001 _**101**_ " forms "101"
No other selection is valid. Thus, there are 6 total ways.

Example 2

1
2
3

Input: s = "11100"
Output: 0
Explanation: It can be shown that there are no valid selections.

Constraints

  • 3 <= s.length <= 10^5
  • s[i] is either '0' or '1'.

Solution

Method 1 – Prefix Sums and Combinatorics

Intuition

We want to select 3 buildings such that no two consecutive selected buildings are of the same type. The only valid patterns are “010” and “101”. For each building in the middle, count the number of valid left and right buildings to form these patterns.

Approach

  1. Precompute prefix sums for the number of ‘0’s and ‘1’s up to each index.
  2. For each building at index i (as the middle building), if s[i] == ‘0’, count the number of ‘1’s to the left and right to form “101”; if s[i] == ‘1’, count the number of ‘0’s to the left and right to form “010”.
  3. For each i, add left_count * right_count to the answer.
  4. Return the total count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    long long numberOfWays(string s) {
        int n = s.size();
        vector<long long> pre0(n+1), pre1(n+1);
        for (int i = 0; i < n; ++i) {
            pre0[i+1] = pre0[i] + (s[i] == '0');
            pre1[i+1] = pre1[i] + (s[i] == '1');
        }
        long long ans = 0;
        for (int i = 1; i < n-1; ++i) {
            if (s[i] == '0') {
                ans += pre1[i] * (pre1[n] - pre1[i+1]);
            } else {
                ans += pre0[i] * (pre0[n] - pre0[i+1]);
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func numberOfWays(s string) int64 {
    n := len(s)
    pre0 := make([]int, n+1)
    pre1 := make([]int, n+1)
    for i := 0; i < n; i++ {
        pre0[i+1] = pre0[i]
        pre1[i+1] = pre1[i]
        if s[i] == '0' {
            pre0[i+1]++
        } else {
            pre1[i+1]++
        }
    }
    var ans int64
    for i := 1; i < n-1; i++ {
        if s[i] == '0' {
            ans += int64(pre1[i]) * int64(pre1[n]-pre1[i+1])
        } else {
            ans += int64(pre0[i]) * int64(pre0[n]-pre0[i+1])
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public long numberOfWays(String s) {
        int n = s.length();
        long[] pre0 = new long[n+1], pre1 = new long[n+1];
        for (int i = 0; i < n; i++) {
            pre0[i+1] = pre0[i] + (s.charAt(i) == '0' ? 1 : 0);
            pre1[i+1] = pre1[i] + (s.charAt(i) == '1' ? 1 : 0);
        }
        long ans = 0;
        for (int i = 1; i < n-1; i++) {
            if (s.charAt(i) == '0') {
                ans += pre1[i] * (pre1[n] - pre1[i+1]);
            } else {
                ans += pre0[i] * (pre0[n] - pre0[i+1]);
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun numberOfWays(s: String): Long {
        val n = s.length
        val pre0 = LongArray(n+1)
        val pre1 = LongArray(n+1)
        for (i in 0 until n) {
            pre0[i+1] = pre0[i] + if (s[i] == '0') 1 else 0
            pre1[i+1] = pre1[i] + if (s[i] == '1') 1 else 0
        }
        var ans = 0L
        for (i in 1 until n-1) {
            if (s[i] == '0') {
                ans += pre1[i] * (pre1[n] - pre1[i+1])
            } else {
                ans += pre0[i] * (pre0[n] - pre0[i+1])
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def numberOfWays(self, s: str) -> int:
        n = len(s)
        pre0 = [0]*(n+1)
        pre1 = [0]*(n+1)
        for i in range(n):
            pre0[i+1] = pre0[i] + (s[i] == '0')
            pre1[i+1] = pre1[i] + (s[i] == '1')
        ans = 0
        for i in range(1, n-1):
            if s[i] == '0':
                ans += pre1[i] * (pre1[n] - pre1[i+1])
            else:
                ans += pre0[i] * (pre0[n] - pre0[i+1])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn number_of_ways(s: String) -> i64 {
        let n = s.len();
        let s = s.as_bytes();
        let mut pre0 = vec![0; n+1];
        let mut pre1 = vec![0; n+1];
        for i in 0..n {
            pre0[i+1] = pre0[i] + if s[i] == b'0' { 1 } else { 0 };
            pre1[i+1] = pre1[i] + if s[i] == b'1' { 1 } else { 0 };
        }
        let mut ans = 0i64;
        for i in 1..n-1 {
            if s[i] == b'0' {
                ans += pre1[i] as i64 * (pre1[n] - pre1[i+1]) as i64;
            } else {
                ans += pre0[i] as i64 * (pre0[n] - pre0[i+1]) as i64;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    numberOfWays(s: string): number {
        const n = s.length
        const pre0 = new Array(n+1).fill(0)
        const pre1 = new Array(n+1).fill(0)
        for (let i = 0; i < n; i++) {
            pre0[i+1] = pre0[i] + (s[i] === '0' ? 1 : 0)
            pre1[i+1] = pre1[i] + (s[i] === '1' ? 1 : 0)
        }
        let ans = 0
        for (let i = 1; i < n-1; i++) {
            if (s[i] === '0') {
                ans += pre1[i] * (pre1[n] - pre1[i+1])
            } else {
                ans += pre0[i] * (pre0[n] - pre0[i+1])
            }
        }
        return ans
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of s. All operations are linear.
  • 🧺 Space complexity: O(n), for the prefix sum arrays.