Is Count Good Strings easy or hard?

Count Good Strings is rated Hard because the difficulty lies in defining the correct DP state, not in the code itself. Once you identify the state and transitions, the implementation is short and runs in linear time.

How to solve Count Good Strings in O(n)?

Define a DP state that captures everything a prefix needs to know about the good-string rule. Iterate from length 0 to n, compute each new value from earlier values using a running prefix sum, and take the result modulo 10^9 + 7 after every addition. Return the value for the target length.

Count Good Strings Python and Java solution?

Both languages use the same bottom-up DP loop. In Python, use integer arithmetic with the modulo applied after each update, and in Java use long to avoid overflow before taking the modulo. The full working code for both is available in the solution tabs on FleetCode.

What is the best approach for Count Good Strings?

The best approach is bottom-up dynamic programming with prefix sums. It builds counts length by length, keeps only the few values needed for the next step, and runs in O(n) time with O(1) extra space. Start from a memoized recursion if the state transitions are not yet clear.

What data structure is used in Count Good Strings?

The main structure is a one-dimensional or two-dimensional DP array, or a hash map for memoization. The optimal version uses only a few scalar variables to store the last values, along with a running prefix sum. No heavy data structures like trees or heaps are required.

What is the time complexity of Count Good Strings?

The optimal solution runs in O(n) time, where n is the target length, because each length is computed once in constant time using prefix sums. Brute force enumeration is exponential, O(2^n * n), and memoized recursion is O(n * k) where k is the number of states per position.

Is Count Good Strings asked at Google, Amazon, or Meta?

Count Good Strings is a counting and dynamic programming problem, and similar string-counting questions appear in interviews at large tech companies. Check company-tagged question lists on FleetCode for the latest reported frequency, since this problem is tagged General on the platform.

4073. Count Good Strings - Practice Online

You are given an integer n.

A string is considered good if it consists only of the characters 'a' and 'b', and one of the following holds:

It contains exactly one distinct character, and its length is odd.
It can be written as s = s1 + s2, where s1 and s2 are non-empty good strings, and the last character of s1 is different from the first character of s2.

Return the number of good strings of length n, modulo 10⁹ + 7.

Here, + denotes string concatenation.

Example 1:

Input: n = 4

Output: 6

Explanation:

The good strings are "aaab", "abbb", "baaa", "bbba", "abab", and "baba".
For example, "aaab" = "aaa" + "b". Both parts are good because each contains one distinct character and has odd length, and their characters at the boundary are different.
Also, "ab" = "a" + "b" is good, so "abab" = "ab" + "ab" is good because the boundary characters are different.
Thus, the answer is 6.

Example 2:

Input: n = 3

Output: 4

Explanation:

The good strings are "aaa", "bbb", "aba", and "bab". Thus, the answer is 4.

Example 3:

Input: n = 2

Output: 2

Explanation:

The good strings are "ab" and "ba". Thus, the answer is 2.

Constraints:

1 <= n <= 10¹⁵