Skip to content

2466. Count Ways To Build Good Strings

Description

Given the integers zero, one, low, and high, we can construct a string by starting with an empty string, and then at each step perform either of the following:

  • Append the character '0' zero times.
  • Append the character '1' one times.

This can be performed any number of times.

A good string is a string constructed by the above process having a length between low and high (inclusive).

Return the number of different good strings that can be constructed satisfying these properties. Since the answer can be large, return it modulo 109 + 7.

 

Example 1:

Input: low = 3, high = 3, zero = 1, one = 1
Output: 8
Explanation: 
One possible valid good string is "011". 
It can be constructed as follows: "" -> "0" -> "01" -> "011". 
All binary strings from "000" to "111" are good strings in this example.

Example 2:

Input: low = 2, high = 3, zero = 1, one = 2
Output: 5
Explanation: The good strings are "00", "11", "000", "110", and "011".

 

Constraints:

  • 1 <= low <= high <= 105
  • 1 <= zero, one <= low

Solutions

Thinking

Each step appends \(zero\) zeros or \(one\) ones; a string is good if its length lies in \([low,high]\). With \(high\le 10^5\), \(dfs(i)\) is the number of ways after length \(i\): count \(1\) if \(i\) is already in range, then add \(dfs(i+zero)\) and \(dfs(i+one)\).

We design a function \(dfs(i)\) to represent the number of good strings constructed starting from the \(i\)-th position. The answer is \(dfs(0)\).

The computation process of the function \(dfs(i)\) is as follows:

  • If \(i > high\), return \(0\);
  • If \(low \leq i \leq high\), increment the answer by \(1\), then after \(i\), we can add either zero number of \(0\)s or one number of \(1\)s. Therefore, the answer is incremented by \(dfs(i + zero) + dfs(i + one)\).

During the process, we need to take the modulus of the answer, and we can use memoization search to reduce redundant computations.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n = high\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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)
}

Solution 2: Dynamic programming

Thinking

Method 1 recurses on the current length. Let \(f[i]\) be ways to reach length \(i\), \(f[0]=1\), from \(f[i-zero]\) and \(f[i-one]\), then sum \(f\) on \([low,high]\). No recursion stack.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @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;
}

Comments