#### Discover more from DMITRII’s Substack

I post a problem that I solve every single day

Continue reading

# # 13.05.2023 [2466. Count Ways To Build Good Strings]

# 13.05.2023

2466. Count Ways To Build Good Strings medium

blog post

#### Join me on Telegram

https://t.me/leetcode_daily_unstoppable/211

#### Problem

Count distinct strings, length low to high, appending ‘0’ zero or ‘1’ one times. Return count % 1,000,000,007.

#### Intuition

Let’s add `zero`

's or `one`

's one by one. For each current length, the resulting count is independent of all the previous additions. We can cache the result by the current `size`

of the string.

#### Approach

Let’s write a DFS solution, adding `zero`

or `one`

and count the good strings.

Then we can rewrite it to the iterative DP.

#### Complexity

Time complexity:

O(n)Space complexity:

O(n)

#### Code

top-down:

```
fun countGoodStrings(low: Int, high: Int, zero: Int, one: Int): Int {
val m = 1_000_000_007
val cache = mutableMapOf<Int, Int>()
fun dfs(currSize: Int): Int {
if (currSize > high) return 0
return cache.getOrPut(currSize) {
val curr = if (currSize in low..high) 1 else 0
val addZeros = if (zero > 0) dfs(currSize + zero) else 0
val addOnes = if (one > 0) dfs(currSize + one) else 0
(curr + addZeros + addOnes) % m
}
}
return dfs(0)
}
```

bottom-up

```
fun countGoodStrings(low: Int, high: Int, zero: Int, one: Int): Int {
val cache = mutableMapOf<Int, Int>()
for (sz in high downTo 0)
cache[sz] = ((if (sz >= low) 1 else 0)
+ (cache[sz + zero]?:0)
+ (cache[sz + one]?:0)) % 1_000_000_007
return cache[0]!!
}
```