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

来源第 91 场双周赛 Q2难度中等分数1694

题目描述

给你整数 zero ，one ，low 和 high ，我们从空字符串开始构造一个字符串，每一步执行下面操作中的一种：

将 '0' 在字符串末尾添加 zero 次。
将 '1' 在字符串末尾添加 one 次。

以上操作可以执行任意次。

如果通过以上过程得到一个长度在 low 和 high 之间（包含上下边界）的字符串，那么这个字符串我们称为好字符串。

请你返回满足以上要求的不同好字符串数目。由于答案可能很大，请将结果对 10⁹ + 7 取余后返回。

示例 1：

输入：low = 3, high = 3, zero = 1, one = 1
输出：8
解释：
一个可能的好字符串是 "011" 。
可以这样构造得到："" -> "0" -> "01" -> "011" 。
从 "000" 到 "111" 之间所有的二进制字符串都是好字符串。

示例 2：

输入：low = 2, high = 3, zero = 1, one = 2
输出：5
解释：好字符串为 "00" ，"11" ，"000" ，"110" 和 "011" 。

提示：

1 <= low <= high <= 10⁵
1 <= zero, one <= low

解法

方法一：记忆化搜索

思考

每次追加 $zero$ 个 $0$ 或 $one$ 个 $1$，长度落在 $[low,high]$ 即好串。 $high \le 10^5$，令 $dfs(i)$ 为已拼出长度 $i$ 时的方案：若 $i$ 已在区间内先计 $1$，再分支 $i+zero$ 与 $i+one$。越界为 $0$。

我们设计一个函数 $dfs(i)$ 表示从第 $i$ 位开始构造的好字符串的个数，答案即为 $dfs(0)$。

函数 $dfs(i)$ 的计算过程如下：

如果 $i \gt high$，返回 $0$；
如果 $ low \leq i \leq high$，答案累加 $1$，然后 $i$ 之后既可以添加 zero 个 $0$，也可以添加 one 个 $1$，因此答案累加上 $dfs(i + zero) + dfs(i + one)$。

过程中，我们需要对答案取模，并且可以使用记忆化搜索减少重复计算。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n = high$。

Python3JavaC++Go

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        @cache
        def dfs(i):
            if i > high:
                return 0
            ans = 0
            if low <= i <= high:
                ans += 1
            ans += dfs(i + zero) + dfs(i + one)
            return ans % mod

        mod = 10**9 + 7
        return dfs(0)

class Solution {
    private static final int MOD = (int) 1e9 + 7;
    private int[] f;
    private int lo;
    private int hi;
    private int zero;
    private int one;

    public int countGoodStrings(int low, int high, int zero, int one) {
        f = new int[high + 1];
        Arrays.fill(f, -1);
        lo = low;
        hi = high;
        this.zero = zero;
        this.one = one;
        return dfs(0);
    }

    private int dfs(int i) {
        if (i > hi) {
            return 0;
        }
        if (f[i] != -1) {
            return f[i];
        }
        long ans = 0;
        if (i >= lo && i <= hi) {
            ++ans;
        }
        ans += dfs(i + zero) + dfs(i + one);
        ans %= MOD;
        f[i] = (int) ans;
        return f[i];
    }
}

class Solution {
public:
    const int mod = 1e9 + 7;

    int countGoodStrings(int low, int high, int zero, int one) {
        vector<int> f(high + 1, -1);
        function<int(int)> dfs = [&](int i) -> int {
            if (i > high) return 0;
            if (f[i] != -1) return f[i];
            long ans = i >= low && i <= high;
            ans += dfs(i + zero) + dfs(i + one);
            ans %= mod;
            f[i] = ans;
            return ans;
        };
        return dfs(0);
    }
};

func countGoodStrings(low int, high int, zero int, one int) int {
    f := make([]int, high+1)
    for i := range f {
        f[i] = -1
    }
    const mod int = 1e9 + 7
    var dfs func(i int) int
    dfs = func(i int) int {
        if i > high {
            return 0
        }
        if f[i] != -1 {
            return f[i]
        }
        ans := 0
        if i >= low && i <= high {
            ans++
        }
        ans += dfs(i+zero) + dfs(i+one)
        ans %= mod
        f[i] = ans
        return ans
    }
    return dfs(0)
}

方法二：动态规划

思考

方法一从长度 $high$ 往回填后缀表，$f[i]$ 是当前长度已为 $i$ 时还能得到的好串数。同一批字符串也可以按恰好拼到长度 $i$ 来数：$f[0]=1$，由 $f[i-zero]$ 与 $f[i-one]$ 转入，再把 $[low,high]$ 上的 $f$ 求和。

自左向右填表，时间仍为 $O(n)$。

TypeScriptJavaScript

function countGoodStrings(low: number, high: number, zero: number, one: number): number {
    const mod = 10 ** 9 + 7;
    const f: number[] = new Array(high + 1).fill(0);
    f[0] = 1;

    for (let i = 1; i <= high; i++) {
        if (i >= zero) f[i] += f[i - zero];
        if (i >= one) f[i] += f[i - one];
        f[i] %= mod;
    }

    const ans = f.slice(low, high + 1).reduce((acc, cur) => acc + cur, 0);

    return ans % mod;
}

/**
 * @param {number} low
 * @param {number} high
 * @param {number} zero
 * @param {number} one
 * @return {number}
 */
function countGoodStrings(low, high, zero, one) {
    const mod = 10 ** 9 + 7;
    const f = Array(high + 1).fill(0);
    f[0] = 1;

    for (let i = 1; i <= high; i++) {
        if (i >= zero) f[i] += f[i - zero];
        if (i >= one) f[i] += f[i - one];
        f[i] %= mod;
    }

    const ans = f.slice(low, high + 1).reduce((acc, cur) => acc + cur, 0);

    return ans % mod;
}

方法三：动态规划

思考

每次追加 $zero$ 个 $0$ 或 $one$ 个 $1$，长度落在 $[low,high]$ 才是好串。$high \le 10^5$，按追加顺序展开会重复大量长度。

较短的那一档总是先递归。$zero$ 与 $one$ 都不小于 $1$，这次调用一定走向更大的长度，最坏调用链长度为 $high$，栈会溢出。

更长的长度在从 $high$ 往 $0$ 填时已经就绪。令 $f[i]$ 为当前长度已是 $i$ 时的好串数：区间内先计 $1$，再加上 $f[i+zero]$ 与 $f[i+one]$，越过 $high$ 的项视为 $0$。

令 $f[i]$ 表示当前长度已经是 $i$ 时，能够构造出的好字符串个数。答案为 $f[0]$。长度超过 $high$ 的贡献为 $0$。

从 $i = high$ 填到 $0$。若 $low \le i \le high$，当前字符串本身就是好串，先计入 $1$。之后仍可追加 $zero$ 个 $0$ 或 $one$ 个 $1$，把 $f[i + zero]$ 与 $f[i + one]$ 加进来；下标超过 $high$ 时该项为 $0$。每一步都对 $10^9 + 7$ 取模。