Count Ways To Build Good Strings

Count Ways To Build Good Strings

What is this problem about?

In the Count Ways To Build Good Strings coding problem, you are building a string starting from an empty one. In each step, you can either append the character '0' exactly zero times or the character '1' exactly one times. You are given a range [low, high]. A string is "good" if its length is between low and high (inclusive). You need to find the total number of unique good strings you can construct.

Why is this asked in interviews?

Companies like Meta and Amazon ask this Dynamic Programming interview pattern to test your ability to solve a variation of the "Climbing Stairs" or "Coin Change" problem. It evaluates if you can identify that the content of the string doesn't matter—only its length. It's a test of whether you can reduce a string construction problem to a numeric counting problem.

Algorithmic pattern used

This problem is solved using 1D Dynamic Programming.

1. Let dp[i] be the number of ways to build a string of length i.
2. Base case: dp[0] = 1 (one way to build an empty string).
3. Transition: dp[i] = (dp[i - zero] + dp[i - one]) % MOD.
4. This is only applicable if i >= zero or i >= one.
5. Finally, sum up dp[i] for all i in the range [low, high].

Example explanation

low = 3, high = 3, zero = 1, one = 2

• dp[0] = 1
• dp[1]: Can only use zero. dp[1] = dp[1-1] = 1. (String "0")
• dp[2]: Can use zero (from len 1) or one (from len 0). dp[2] = dp[1] + dp[0] = 1 + 1 = 2. (Strings "00", "11")
• dp[3]: Can use zero (from len 2) or one (from len 1). dp[3] = dp[2] + dp[1] = 2 + 1 = 3. (Strings "000", "110", "011") Result for length 3 is 3.

Common mistakes candidates make

• String Generation: Trying to actually build and store the strings, which leads to memory exhaustion and TLE.
• Range Summing: Forgetting to sum all dp values in the range [low, high] and only returning dp[high].
• Modulo: Not applying the modulo consistently, especially during the final summation.

Interview preparation tip

When a problem asks for "number of ways" to reach a certain size or sum, and you have fixed increments, think of DP. It's almost always a variation of the Fibonacci sequence.