Skip to content

2466. Count Ways To Build Good Strings

SourceBiweekly Contest 91 Q2DifficultyMediumRating1694

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 \(\textit{zero}\) zeros or \(\textit{one}\) ones; a string is good if its length lies in \([\textit{low},\textit{high}]\). With \(\textit{high}\le 10^5\), \(\textit{dfs}(i)\) is the number of ways after length \(i\): count \(1\) if \(i\) is already in range, then add \(\textit{dfs}(i+\textit{zero})\) and \(\textit{dfs}(i+\textit{one})\).

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

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

  • If \(i > \textit{high}\), return \(0\);
  • If \(\textit{low} \leq i \leq \textit{high}\), increment the answer by \(1\), then after \(i\), we can add either \(\textit{zero}\) number of \(0\)s or \(\textit{one}\) number of \(1\)s. Therefore, the answer is incremented by \(\textit{dfs}(i + \textit{zero}) + \textit{dfs}(i + \textit{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)\), where \(n = \textit{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 fills a suffix table from length \(\textit{high}\). The same strings can be counted by the ways to reach each length: \(f[0]=1\), add \(f[i-\textit{zero}]\) and \(f[i-\textit{one}]\), then sum \(f\) on \([\textit{low},\textit{high}]\).

Fill left to right. Time stays \(O(n)\).

 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;
}

Solution 3: Dynamic Programming

Thinking

Each step appends \(\textit{zero}\) zeros or \(\textit{one}\) ones, and a string is good when its length lies in \([\textit{low},\textit{high}]\). \(\textit{high} \le 10^5\), so a decision tree over appends repeats many lengths.

The shorter step is taken first. Both steps are at least \(1\), so that call always moves to a larger length, and the chain can have length \(\textit{high}\) and overflow the stack.

Longer lengths are known if we walk downward. Let \(f[i]\) be the number of good strings when the length is already \(i\): count \(1\) inside the range, then add \(f[i+\textit{zero}]\) and \(f[i+\textit{one}]\), treating anything past \(\textit{high}\) as \(0\).

Let \(f[i]\) be the number of good strings that can be built when the current length is already \(i\). The answer is \(f[0]\). Lengths past \(\textit{high}\) contribute \(0\).

Fill \(i\) from \(\textit{high}\) down to \(0\). If \(\textit{low} \le i \le \textit{high}\), the current string is already good, so start from \(1\). Then add \(f[i + \textit{zero}]\) and \(f[i + \textit{one}]\); an index past \(\textit{high}\) contributes \(0\). Reduce each value modulo \(10^9 + 7\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n = \textit{high}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        mod = 10**9 + 7
        f = [0] * (high + 1)
        for i in range(high, -1, -1):
            ans = int(low <= i <= high)
            if i + zero <= high:
                ans += f[i + zero]
            if i + one <= high:
                ans += f[i + one]
            f[i] = ans % mod
        return f[0]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    private static final int MOD = (int) 1e9 + 7;

    public int countGoodStrings(int low, int high, int zero, int one) {
        int[] f = new int[high + 1];
        for (int i = high; i >= 0; --i) {
            long ans = i >= low && i <= high ? 1 : 0;
            if (i + zero <= high) {
                ans += f[i + zero];
            }
            if (i + one <= high) {
                ans += f[i + one];
            }
            f[i] = (int) (ans % MOD);
        }
        return f[0];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    const int mod = 1e9 + 7;

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func countGoodStrings(low int, high int, zero int, one int) int {
    const mod int = 1e9 + 7
    f := make([]int, high+1)
    for i := high; i >= 0; i-- {
        ans := 0
        if i >= low && i <= high {
            ans++
        }
        if i+zero <= high {
            ans += f[i+zero]
        }
        if i+one <= high {
            ans += f[i+one]
        }
        f[i] = ans % mod
    }
    return f[0]
}

Comments