Count Good Strings - Solution & Explanation

Problem Overview: You are given a length constraint and a rule that decides whether a string is good. Count how many strings satisfy the rule, modulo 10^9 + 7. Brute force fails because the number of candidate strings grows exponentially with length.

Approach 1: Brute Force Enumeration (O(2^n * n) time, O(n) space)

Generate every string of the target length over the allowed alphabet with recursion or backtracking. For each complete string, run the goodness check, which scans the string once. This is correct because it touches every candidate, but the candidate count doubles with each extra character. Use it only to validate outputs on small inputs while you derive the recurrence.

Approach 2: Memoized Recursion on State (O(n * k) time, O(n * k) space)

Notice that whether a prefix can still lead to a good string depends only on a small state, such as the current length and a few counters that track the rule. Define dp(pos, state) as the number of valid completions from that point. Cache results in a hash map or 2D array so each state is computed once. This turns exponential enumeration into a polynomial number of distinct subproblems. It is the fastest route to a correct answer when the state space is clear, and it is easy to verify against the brute force. Review the dynamic programming patterns if the state transitions feel unclear.

Approach 3: Bottom-Up DP with Prefix Sums (O(n) time, O(1) extra space)

Replace recursion with an iterative table that builds counts from length 0 up to the target. Each new length is derived from earlier lengths by adding a fixed set of transitions, and you can accumulate them with a running prefix sum over a window of previous values instead of summing from scratch. This removes recursion overhead and keeps only the last few values, which is why it is the expected final answer. Take the modulo after every addition to avoid overflow. For counting problems over ranges of lengths, the prefix sum technique keeps the update constant time per step.

Recommended for interviews: Interviewers expect you to start with brute force to show you understand the search space, then move to memoized recursion to reveal the state. The bottom-up version with prefix sums demonstrates the skill they are testing. Explain the state definition clearly before you write any code, because most candidates lose time on the transitions rather than the final loop. Practice related string counting problems to build the habit of identifying the minimal state.