What is the main trick in Number of Ways to Select Buildings?

The main trick is noticing that every valid selection must form either 010 or 101. That lets you count alternating subsequences directly instead of testing every triple of indices.

Why is state transition dynamic programming a good fit here?

Because each new character can only affect a small set of partial patterns. A 0 can start 0, extend 1 into 10, and finish 01 into 010, while a 1 does the symmetric work for 1, 01, and 101.

Can this problem be solved with prefix sums too?

Yes. For each position, treat it as the middle building and multiply the count of opposite-type buildings on the left by the count of opposite-type buildings on the right. Summing those products over all indices gives the answer.

Why does s = 001101 return 6?

The valid triples are exactly the subsequences forming 010 or 101. In this string, four selections produce 010 and two selections produce 101, giving a total of 6 valid ways.

What is the most common mistake on this problem?

The most common mistake is thinking the three buildings must be adjacent. They only need increasing indices, so this is a subsequence-counting problem, not a substring or sliding-window problem.

#2222

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

选择建筑的方案数

给你一个下标从 0 开始的二进制字符串 s ，它表示一条街沿途的建筑类型，其中： s[i] = '0' 表示第 i 栋建筑是一栋办公楼， s[i] = '1' 表示第 i 栋建筑是一间餐厅。作为市政厅的官员，你需要随机选择 3 栋建筑。然而，为了确保多样性，选出来的 3 栋建筑相邻的两栋不能…

字符串动态规划前缀和

题目描述

给你一个下标从 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' 。

lightbulb

解题思路

方法一：计数 + 枚举

根据题目描述，我们需要选择 $3$ 栋建筑，且相邻的两栋不能是同一类型。

我们可以枚举中间的建筑，假设为 $x$ ，那么左右两边的建筑类型只能是 $x \oplus 1$ ，其中 $\oplus$ 表示异或运算。因此，我们可以使用两个数组 $l$ 和 $r$ 分别记录左右两边的建筑类型的数量，然后枚举中间的建筑，计算答案即可。

时间复杂度 $O(n)$ ，其中 $n$ 是字符串 $s$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def numberOfWays(self, s: str) -> int:
        l = [0, 0]
        r = [s.count("0"), s.count("1")]
        ans = 0
        for x in map(int, s):
            r[x] -= 1
            ans += l[x ^ 1] * r[x ^ 1]
            l[x] += 1
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They hint that only 010 and 101 matter, which is a direct push away from checking all triples.
question_mark
They ask for a linear solution under length 10^5, so any nested loop over candidate triples is dead on arrival.
question_mark
They mention Dynamic Programming and Prefix Sum together, which usually means counting subsequences through running state totals rather than recursion.

warning

常见陷阱

外企场景

error
Counting contiguous substrings instead of subsequences, which misses valid picks with gaps between buildings.
error
Updating DP states in the wrong order and accidentally reusing the current character twice in one transition.
error
Using a 32-bit integer even though the number of valid triples can grow large for long strings.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count alternating subsequences of length k instead of exactly three buildings.
arrow_right_alt
Return separate counts for pattern 010 and pattern 101 rather than their total.
arrow_right_alt
Generalize from a binary string to a small alphabet and count subsequences with no equal adjacent selected characters.

help

常见问题

外企场景

继续练习

#2209 用地毯覆盖后的最少白色砖块 #1871 跳跃游戏 VII #2218 从栈中取出 K 个硬币的最大面值和