LeetCode 2466. 统计构造好字符串的方案数

2026-09-13 HGNULB 约 4 分钟

文章信息 2 个分类 1 个标签

分类

LeetCode 中等

题目描述

✅ 2466. 统计构造好字符串的方案数

题意分析

从空串出发，每次追加 zero 个字符 '0'，或追加 one 个字符 '1'，统计长度落在闭区间 [low, high] 内的不同字符串数量。两种追加长度都为正，答案对 $10^9+7$ 取模。

相同长度的字符串可以采用相同的后续操作，因此只需记录每种长度的方案数，不必保存实际字符串。

解法：按最终长度递推两种追加方式

核心思路

[!blue]

定义 dp[length] 为恰好能构造出长度 length 的不同字符串数量。从最后一步分类：若最后追加零段，就来自 dp[length - zero]；若最后追加一段，就来自 dp[length - one]。长度不足以容纳对应段时，这个来源不存在。

同一种追加操作不会合并不同前缀：在不同字符串后接上相同固定段，结果仍然不同。两种操作的结果又分别以 '0'、'1' 结尾，互不重叠；反过来，从结果末尾删去固定长度的对应段，前驱也唯一。因此直接相加既不重复，也不会遗漏任何字符串。

即使 zero == one，两种操作也会追加不同字符，必须分别计数。状态按长度合并只是把数量放在一起，没有把这些不同字符串去重成一种。

初始化 dp[0] = 1，表示唯一的空串。由于每次追加长度为正，当前状态只依赖更短长度，可以从 $1$ 递推到 high。每个长度都先计算完整方案数，再在它不小于 low 时加入总答案；低于 low 的状态仍要计算，作为后续状态的前驱。

解题步骤

创建长度为 high + 1 的全零数组，将 dp[0] 设为 $1$。

按长度递增，分别判断能否去掉最后的零段和一段，将合法前驱的数量相加并取模。

当前长度位于 [low, high] 时，把 dp[length] 累加到答案并取模。

扫描完 high 后返回答案。无法构造的长度保持 $0$；题目中 low >= 1，空串只作为起点，不计入答案。

代码实现

class Solution {
    public int countGoodStrings(int low, int high, int zero, int one) {
        int mod = 1_000_000_007;
        int answer = 0;
        int[] dp = new int[high + 1];

        dp[0] = 1;

        for (int length = 1; length <= high; length++) {
            if (length >= zero) {
                dp[length] = dp[length - zero];
            }

            if (length >= one) {
                dp[length] = (dp[length] + dp[length - one]) % mod;
            }

            if (length >= low) {
                answer = (answer + dp[length]) % mod;
            }
        }

        return answer;
    }
}

func countGoodStrings(low, high, zero, one int) int {
    const mod = 1000000007
    dp := make([]int, high+1)
    dp[0] = 1
    answer := 0
    for length := 1; length <= high; length++ {
        if length >= zero {
            dp[length] = dp[length-zero]
        }
        if length >= one {
            dp[length] = (dp[length] + dp[length-one]) % mod
        }
        if length >= low {
            answer = (answer + dp[length]) % mod
        }
    }
    return answer
}

复杂度分析

时间复杂度：$O(high)$，每个长度只处理两个前驱并至多累加一次答案。

空间复杂度：$O(high)$，保存各长度的方案数。

关键点总结

[!green]

按最后追加的字符段分类，两类结果由末尾字符区分，计数互不重叠。

相同步长仍有两种字符选择，不能合并成一种操作。

从空串计数开始，先得到准确长度的方案数，再汇总目标区间。

易错点总结

[!yellow]

用互斥的 if/else 处理两种追加方式，会漏掉本来都可使用的前驱。

忘记 dp[0] = 1，所有状态都会保持零。

从 low 才开始填表，会漏算需要较短前缀构成的字符串。

累计答案需要包含 low、high 两个端点，并在累加时取模。

相似题目

题目	难度	关联与区别
70. 爬楼梯	简单	同样按长度从较短状态递推，本题两种操作附带不同字符，即使步长相同也有两种选择。
377. 组合总和 Ⅳ	中等	都统计有顺序的构造方案，应先枚举最终长度或总和，再汇总各个最后操作。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/20234935

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！