选择建筑的方案数

难度: Medium

给你一个下标从 0 开始的二进制字符串 s ，它表示一条街沿途的建筑类型，其中：

s[i] = '0' 表示第 i 栋建筑是一栋办公楼，
s[i] = '1' 表示第 i 栋建筑是一间餐厅。

作为市政厅的官员，你需要随机选择 3 栋建筑。然而，为了确保多样性，选出来的 3 栋建筑相邻的两栋不能是同一类型。

比方说，给你 s = "001101" ，我们不能选择第 1 ，3 和 5 栋建筑，因为得到的子序列是 "011" ，有相邻两栋建筑是同一类型，所以不合题意。

请你返回可以选择 3 栋建筑的 有效方案数 。

示例 1：

输入：s = "001101"
输出：6
解释：
以下下标集合是合法的：
- [0,2,4] ，从 "001101" 得到 "010"
- [0,3,4] ，从 "001101" 得到 "010"
- [1,2,4] ，从 "001101" 得到 "010"
- [1,3,4] ，从 "001101" 得到 "010"
- [2,4,5] ，从 "001101" 得到 "101"
- [3,4,5] ，从 "001101" 得到 "101"
没有别的合法选择，所以总共有 6 种方法。

示例 2：

输入：s = "11100"
输出：0
解释：没有任何符合题意的选择。

提示：

3 <= s.length <= 10⁵
s[i] 要么是 '0' ，要么是 '1' 。

Submission

运行时间: 229 ms

内存: 16.7 MB

class Solution:
    def numberOfWays(self, s: str) -> int:
        ans = n0 = n1 = n10 = n01 = 0
        for char in s:
            if char == '1':
                n01 += n0
                n1 += 1
                ans += n10
            else:
                n10 += n1
                n0 += 1
                ans += n01
        return ans

Explain

该题解采用一趟扫描的方式统计有效的三建筑选取方案。定义了几个计数器：n0 (遇到的'0'的数量), n1 (遇到的'1'的数量), n10 ('10'模式的数量), n01 ('01'模式的数量)。遍历字符串s中的每个字符，根据当前字符更新相关计数器。如果当前字符是'1'，则更新n01为n0+n01（即当前1之前所有0的数量都可以和当前1形成'01'模式），n1自增，同时ans累加n10（即之前统计的所有'10'模式数量，每一个都可以与当前的'1'形成'101'模式）。反之，如果当前字符是'0'，类似地更新n10和n0，并增加当前的答案ans值。最终，ans即为所有合法的三字符选择方案数。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def numberOfWays(self, s: str) -> int:
        ans = n0 = n1 = n10 = n01 = 0  # 初始化计数器
        for char in s:  # 遍历字符串s的每个字符
            if char == '1':  # 当前字符为'1'
                n01 += n0  # 更新'01'模式的数量
                n1 += 1  # 更新'1'的数量
                ans += n10  # 增加答案，每个'10'都可以与此'1'形成'101'
            else:  # 当前字符为'0'
                n10 += n1  # 更新'10'模式的数量
                n0 += 1  # 更新'0'的数量
                ans += n01  # 增加答案，每个'01'都可以与此'0'形成'010'
        return ans  # 返回合法的三字符选择方案数

Explore

在算法中，通过特定的计数器逻辑，确保了统计的组合中相邻建筑不是同一类型。当遇到字符'1'时，算法会使用n10（之前累计的'10'模式的数量）来增加答案，表示这些'10'模式都可以与当前的'1'构成'101'。类似地，当遇到'0'时，使用n01（之前累计的'01'模式的数量）来增加答案，表示这些'01'模式都可以与当前的'0'构成'010'。这种方式确保了组合中的每两栋相邻建筑分别为'1'和'0'，不会出现同一类型。

在算法中，计数器具体使用如下： - `n0`用于记录遇到的'0'的总数。 - `n1`用于记录遇到的'1'的总数。 - `n10`用于记录形成的'10'模式的数量，即每次遇到'0'时，将当前的`n1`(之前遇到的所有'1'的数量)加到`n10`上。 - `n01`用于记录形成的'01'模式的数量，即每次遇到'1'时，将当前的`n0`(之前遇到的所有'0'的数量)加到`n01`上。这些计数器帮助追踪和构建必要的字符模式，并用于计算最终的答案。

选择在遇到'1'时累加n10，是因为每个'10'模式都可以与当前的'1'结合形成一个完整的'101'模式，这是一个有效的选择方案。同样，当遇到'0'时累加n01，是因为每个'01'模式都可以与当前的'0'结合形成一个完整的'010'模式。这种计数方法直接关联到目标模式的构成，确保每个计数的增加都对应一个完整且有效的建筑选择方案。