Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2222.html

2222. Number of Ways to Select Buildings (Medium)

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

Solution 1. DP

Let dp[len][c] be the count of alternating subsequences of length len ending with character '0' + c'. The answer is dp[3][0] + dp[3][1].

We can scan the array from left to right and compute these dp[len][c] values.

For each dp[len][c], its count should increase by dp[len - 1][1 - c], i.e. prepending subsequences of length len - 1 ending with a different character.

  • // OJ: https://leetcode.com/problems/number-of-ways-to-select-buildings/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    long long numberOfWays(string s) {
        long dp[4][2] = {};
        dp[0][0] = dp[0][1] = 1;
        for (int i = 0; i < s.size(); ++i) {
            for (int len = 1; len <= 3; ++len) {
                dp[len][s[i] - '0'] += dp[len - 1][1 - (s[i] - '0')]; // for this s[i], we can prepend subsequences of length `len-1` ending with a different character to it.
            }
        }
        return dp[3][0] + dp[3][1];
    }
};

  • class Solution:
    def numberOfWays(self, s: str) -> int:
        n = len(s)
        cnt0 = s.count("0")
        cnt1 = n - cnt0
        c0 = c1 = 0
        ans = 0
        for c in s:
            if c == "0":
                ans += c1 * (cnt1 - c1)
                c0 += 1
            else:
                ans += c0 * (cnt0 - c0)
                c1 += 1
        return ans

############

# 2222. Number of Ways to Select Buildings
# https://leetcode.com/problems/number-of-ways-to-select-buildings/

class Solution:
    def numberOfWays(self, s: str) -> int:
        rZero, rOne = s.count("0"), s.count("1")
        
        lZero = lOne = 0
        res = 0
        
        for x in s:
            if x == "1":
                lOne += 1
                res += lZero * rZero
                rOne -= 1
            else:
                lZero += 1
                res += lOne * rOne
                rZero -= 1

        return res


  • 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;
    }
}

  • func numberOfWays(s string) int64 {
	n := len(s)
	cnt0 := strings.Count(s, "0")
	cnt1 := n - cnt0
	c0, c1 := 0, 0
	ans := 0
	for _, c := range s {
		if c == '0' {
			ans += c1 * (cnt1 - c1)
			c0++
		} else {
			ans += c0 * (cnt0 - c0)
			c1++
		}
	}
	return int64(ans)
}

Discuss

https://leetcode.com/problems/number-of-ways-to-select-buildings/discuss/1907123/

All Problems

All Solutions