How do I approach the Count Ways To Build Good Strings problem?

Start by applying dynamic programming to calculate the number of ways to form valid strings using state transitions, then optimize for space complexity.

What is the time complexity of solving this problem?

The time complexity is O(high) because you calculate the valid strings for each length from 0 to high.

How can I optimize the space complexity of this problem?

You can optimize space by only storing the current and previous states, reducing space complexity from O(high) to O(1).

What are common mistakes when solving this problem?

Common mistakes include not handling edge cases, such as when low equals high, or not optimizing the space complexity.

Can the problem be extended to other types of strings?

Yes, you can modify the problem to count strings with a fixed length, or introduce other operations or characters beyond binary digits.

#2466

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

给你整数 zero ， one ， low 和 high ，我们从空字符串开始构造一个字符串，每一步执行下面操作中的一种：将 '0' 在字符串末尾添加 zero 次。将 '1' 在字符串末尾添加 one 次。以上操作可以执行任意次。如果通过以上过程得到一个长度在 low 和 high 之…

动态规划

题目描述

给你整数 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

lightbulb

解题思路

方法一：记忆化搜索

我们设计一个函数 $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$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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)

speed

复杂度分析

指标	值
时间	O(\text{high})
空间	O(\text{high})

psychology

面试官常问的追问

外企场景

question_mark
Look for the candidate's understanding of dynamic programming and state transitions.
question_mark
Check if the candidate can optimize the space complexity by reducing it to O(1).
question_mark
Evaluate whether the candidate can describe how to handle the edge cases like when low equals high.

warning

常见陷阱

外企场景

error
Overcomplicating the space complexity by not using the state transition optimization.
error
Not handling the case where low equals high correctly, leading to incorrect counting.
error
Confusing the number of valid strings with the number of operations to generate them.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Adjust the problem to only count strings with a fixed length instead of a range.
arrow_right_alt
Introduce a limit on the number of '1' or '0' that can be appended at each step.
arrow_right_alt
Extend the problem to include additional binary operations or different characters.

help

常见问题

外企场景

继续练习

#2463 最小移动总距离 #2472 不重叠回文子字符串的最大数目 #2478 完美分割的方案数