Medium

题目描述

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

  • s[i] = '0' 表示第 i 个建筑物是一个办公楼
  • s[i] = '1' 表示第 i 个建筑物是一个餐厅

作为市政官员，你需要从中选择 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^5
  • s[i] 是 '0' 或 '1'

解题思路

解题思路

这道题要求我们从二进制字符串中选择3个建筑物，使得选中的建筑物类型形成交替模式。仔细分析可知，只有两种有效的3位模式：“010” 和 “101”。

核心思路：动态规划 + 前缀计数

我们可以通过逐步构建子序列的方式来解决这个问题：

  1. 分别统计两种模式：由于只有"010"和"101"两种有效模式，我们可以分别计算这两种模式的数量，最后相加。

  2. 递推构建：

    • 对于模式"010"：先统计"0"的个数，再统计"01"子序列的个数，最后统计"010"子序列的个数
    • 对于模式"101"：先统计"1"的个数，再统计"10"子序列的个数，最后统计"101"子序列的个数

  3. 状态转移：

    • count0[i]：前i个字符中'0’的个数
    • count01[i]：前i个字符中"01"子序列的个数
    • count010[i]：前i个字符中"010"子序列的个数

当遍历到位置i时：

  • 如果s[i] == '1'，则count01[i] = count01[i-1] + count0[i-1]（新增的'1’可以和前面所有的'0’组成"01"）
  • 如果s[i] == '0'，则count010[i] = count010[i-1] + count01[i-1]（新增的'0’可以和前面所有的"01"组成"010"）

优化空间复杂度

我们不需要存储整个数组，只需要维护当前的计数值即可，将空间复杂度优化到O(1)。

代码实现

class Solution {
public:
    long long numberOfWays(string s) {
        long long count0 = 0, count1 = 0;
        long long count01 = 0, count10 = 0;
        long long count010 = 0, count101 = 0;
        
        for (char c : s) {
            if (c == '0') {
                count010 += count01;
                count10 += count1;
                count0++;
            } else {
                count101 += count10;
                count01 += count0;
                count1++;
            }
        }
        
        return count010 + count101;
    }
};

class Solution:
    def numberOfWays(self, s: str) -> int:
        count0 = count1 = 0
        count01 = count10 = 0
        count010 = count101 = 0
        
        for c in s:
            if c == '0':
                count010 += count01
                count10 += count1
                count0 += 1
            else:
                count101 += count10
                count01 += count0
                count1 += 1
        
        return count010 + count101

public class Solution {
    public long NumberOfWays(string s) {
        long count0 = 0, count1 = 0;
        long count01 = 0, count10 = 0;
        long count010 = 0, count101 = 0;
        
        foreach (char c in s) {
            if (c == '0') {
                count010 += count01;
                count10 += count1;
                count0++;
            } else {
                count101 += count10;
                count01 += count0;
                count1++;
            }
        }
        
        return count010 + count101;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var numberOfWays = function(s) {
    let count = 0;
    let zeros = 0;
    let ones = 0;
    let zeroOnes = 0;
    let oneZeros = 0;
    
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '0') {
            count += oneZeros;
            zeroOnes += ones;
            zeros++;
        } else {
            count += zeroOnes;
            oneZeros += zeros;
            ones++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)
空间复杂度O(1)

其中 n 为字符串 s 的长度。我们只需要遍历字符串一次，每次操作都是常数时间，所以时间复杂度为 O(n)。我们只使用了常数个变量来记录计数信息，所以空间复杂度为 O(1)。