算法题：字符串替换计数

问题描述

给定一个长度为 n 的字符串 s，其中每个字符是 A、B、? 之一。需要将每个 ? 独立地替换为 A 或 B，得到一个最终的字符串 t。要求：最终字符串 t 中，每个由相同字符组成的连续子串（即相同字符的连续段）的长度必须为奇数。

计算有多少种不同的替换方案，结果对 10^9+7 取模。

示例：

s = "A?B" → 可能的替换：AAB（AA 段长度为2，不合规）、ABB（BB 段长度为2，不合规）→ 结果为 0
s = "??" → 可能的替换：AA（段长度2，不合规）、AB（A段1奇数，B段1奇数，合规）、BA（合规）、BB（不合规）→ 结果为 2

解题思路

这道题本质上是一个带有约束的字符串构造问题。需要统计所有满足"相同字符连续段长度均为奇数"的替换方案。

关键点分析

"?“的处理：每个 ? 可以独立选择 A 或 B，两种选择都要纳入计数。
连续段的奇偶性约束：将字符串划分为连续的相同字符段（run），每个 run 的长度必须是奇数。
状态转移的特性：当我们在某个位置放置一个字符时，需要知道：
- 若当前位置字符与前一位相同，则当前 run 长度奇偶性翻转（奇→偶，偶→奇）
- 若当前位置字符与前一位不同，则必须满足前一个 run 长度为奇数，然后开启长度为 1（奇数）的新 run
- 最终答案要求最后一个 run 的长度也必须是奇数

算法设计

状态定义：dp[i][c][p]：考虑前 i 个位置，第 i 个位置的字符为 c，且以该字符结尾的连续段长度奇偶性为 p 的方案数

c：0 表示 A，1 表示 B
p：0 表示偶数长度，1 表示奇数长度

状态转移：对于位置 i（从 1 到 n-1），根据 s[i] 可能的取值进行转移：

放置字符 A（当 s[i] 为 A 或 ?）：
- 形成奇数长度 A-run：dp[i][0][1] = dp[i-1][0][0] + dp[i-1][1][1]
  - 从 A 的偶数段延长（偶→奇）
  - 从 B 的奇数段切换过来（旧段结束，新 A 段长度为 1）
- 形成偶数长度 A-run：dp[i][0][0] = dp[i-1][0][1]
  - 只能从 A 的奇数段延长（奇→偶）
放置字符 B（当 s[i] 为 B 或 ?）：
- 形成奇数长度 B-run：dp[i][1][1] = dp[i-1][1][0] + dp[i-1][0][1]，同理
- 形成偶数长度 B-run：dp[i][1][0] = dp[i-1][1][1]，同理

初始化：位置 0，长度为 1 的 run 是奇数

若 s[0] 为 A 或 ?：dp[0][0][1] = 1
若 s[0] 为 B 或 ?：dp[0][1][1] = 1

结果计算： dp[n-1][0][1] + dp[n-1][1][1]（最后一个 run 必须是奇数长度）

代码实现

MOD = 10**9 + 7

n = eval(input())
s = input()

# dp[i][c][p]
# i: cur index
# c: 0 for A, 1 for B at cur index
# p: 0 for even, 1 for odd at cur run
dp = [[[0, 0] for _ in range(2)] for _ in range(n)]
if s[0] == "A" or s[0] == "?":
    dp[0][0][1] = 1
    dp[0][0][0] = 0
if s[0] == "B" or s[0] == "?":
    dp[0][1][1] = 1
    dp[0][1][0] = 0

for i in range(1, n):
    if s[i] == "A" or s[i] == "?":
        dp[i][0][1] = (dp[i - 1][0][0] + dp[i - 1][1][1]) % MOD
        dp[i][0][0] = dp[i - 1][0][1]

    if s[i] == "B" or s[i] == "?":
        dp[i][1][1] = (dp[i - 1][1][0] + dp[i - 1][0][1]) % MOD
        dp[i][1][0] = dp[i - 1][1][1]

res = (dp[n - 1][0][1] + dp[n - 1][1][1]) % MOD
print(res)

测试用例

输入：
5
A???B?
# AAABBB
# ABABBB
# ABBBBB

输出：
3

算法分析

时间复杂度：O(n)，n 为字符串长度。每个位置只需进行常数次状态转移。

空间复杂度：O(n)，需要存储大小为 n×2×2 的 DP 数组。可以优化为 O(1)（使用滚动数组），但三维形式更易于理解。

prev = [[0, 0], [0, 0]]  # prev[char][parity]
if s[0] == 'A' or s[0] == '?':
    prev[0][1] = 1
if s[0] == 'B' or s[0] == '?':
    prev[1][1] = 1

for i in range(1, n):
    cur = [[0, 0], [0, 0]]
    if s[i] == 'A' or s[i] == '?':
        cur[0][1] = (prev[0][0] + prev[1][1]) % MOD
        cur[0][0] = prev[0][1]
    if s[i] == 'B' or s[i] == '?':
        cur[1][1] = (prev[1][0] + prev[0][1]) % MOD
        cur[1][0] = prev[1][1]
    prev = cur

result = (prev[0][1] + prev[1][1]) % MOD

关键点总结

三维DP状态设计：用（位置，当前字符，奇偶性）完整刻画问题状态，使转移逻辑清晰。
奇数约束的体现：只有当前 run 为奇数时才能切换字符，确保每个 run 结束时长度合规。
对称性处理：A 和 B 的状态转移完全对称，代码复用性高。
”?“的通配处理：通过条件判断 if s[i] == 'A' or s[i] == '?' 优雅地处理 ? 的两种选择。
模运算：题目要求对 10^9+7 取模，在每次加法后立即取模避免溢出。

扩展思考

如果字符种类更多（如 A、B、C）：状态数会从 2×2 变为 k×2（k为字符种类数），但仍然可以套用相同框架。
如果要求偶数长度段：只需在结果取 dp[n-1][c][0] 即可。
如果要求最大/最小字典序方案：可以在 DP 计数的基础上，结合贪心策略回溯构造具体方案。
如果”?“存在概率分布：可以将 DP 中的加法改为权重求和，用期望值替代计数。

问题描述#

解题思路#

关键点分析#

算法设计#

代码实现#

测试用例#

算法分析#

关键点总结#

扩展思考#