Number of Good Binary Strings - Solution & Explanation

Problem Overview: You need to count how many binary strings have a length between low and high. The string can only be built by repeatedly appending a block of zero zeros or a block of one ones. The result can grow very large, so return the count modulo 1e9 + 7.

Approach 1: Recursion with Memoization (Top-Down DP) (Time: O(high), Space: O(high))

Think of the problem as building the string length step by step. From a current length len, you can move to len + zero or len + one. A recursive function explores these possibilities until the length exceeds high. Memoization stores the result for each length so repeated states are not recomputed. The key insight is that the number of valid strings depends only on the current length, not on the actual characters used. This turns the recursion tree into a linear number of states.

Approach 2: Bottom-Up Dynamic Programming (Time: O(high), Space: O(high))

Create a DP array where dp[i] represents the number of ways to build a string of length i. Initialize dp[0] = 1 since there is one way to build an empty string. Iterate from length 1 to high, and update dp[i] using previous states: add dp[i - zero] if i >= zero and add dp[i - one] if i >= one. Whenever i falls between low and high, include dp[i] in the final answer. This approach avoids recursion and directly builds the solution using dynamic programming.

Approach 3: Space-Optimized DP Counting (Time: O(high), Space: O(high))

The transition only depends on earlier lengths, so the DP can be computed sequentially without storing additional structures. Maintain a single array up to high and accumulate results during iteration. The algorithm still uses the same recurrence but focuses on minimizing overhead and improving clarity. The logic resembles counting paths in a graph where nodes represent lengths and edges represent valid extensions.

Recommended for interviews: The bottom-up DP solution is what interviewers expect. It clearly shows that you recognized the recurrence relation and implemented an efficient state transition. Explaining the recursive formulation first demonstrates understanding of the state space, while converting it to an iterative dynamic programming solution shows practical problem-solving skill. Problems like this often appear alongside other state-transition questions involving memoization and counting paths.