DMITRII’s Substack

Share this post

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

dmitriisamoilenko.substack.com

Discover more from DMITRII’s Substack

I post a problem that I solve every single day
Continue reading
Sign in

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

DMITRII SAMOILENKO
May 13, 2023
Share this post

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

dmitriisamoilenko.substack.com
Share

13.05.2023

2466. Count Ways To Build Good Strings medium
blog post

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/211

Thanks for reading DMITRII’s Substack! Subscribe for free to receive new posts and support my work.

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]!!
}

Thanks for reading DMITRII’s Substack! Subscribe for free to receive new posts and support my work.

Share this post

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

dmitriisamoilenko.substack.com
Share
Previous
Next
Comments
Top
New

No posts

Ready for more?

© 2023 DMITRII SAMOILENKO
Privacy ∙ Terms ∙ Collection notice
Start WritingGet the app
Substack is the home for great writing