Number of ways to select buildings

String Dynamic Programming Prefix Sum

50.9% acceptance

Feb 25, 2026

1058

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_ways(s: String) -> i64 {
    let mut ways = 0i64;
    let mut c0 = 0i64; // count of '0' seen so far
    let mut c1 = 0i64; // count of '1' seen so far
    let mut c01 = 0i64; // count of "01" subsequences seen
    let mut c10 = 0i64; // count of "10" subsequences seen
    for b in s.bytes() {
      if b == b'0' {
        ways += c10; // "010" subsequence: for each "10" before, can append '0'
        c01 += c1;   // extend "01" count
        c0 += 1;
      } else {
        ways += c01; // "101" subsequence
        c10 += c0;
        c1 += 1;
      }
    }
    ways
  }
}