We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Good Binary Strings

Number: 2672

Difficulty: Medium

Paid? Yes

Companies: Citadel, Expedia

Problem Description

Given four integers – minLength, maxLength, oneGroup, and zeroGroup – count the number of binary strings whose lengths are between minLength and maxLength (inclusive) and in which every block (maximal contiguous segment) of 1’s has a length that is a multiple of oneGroup and every block of 0’s has a length that is a multiple of zeroGroup. (Note: if a digit does not appear at all, that is acceptable since 0 is considered a multiple of every number.) Return the answer modulo 10^9 + 7.

Key Insights

  • The valid string is essentially formed by alternating “blocks” where each block is a sequence of identical characters.
  • Each block must have a length that is a positive multiple of its given “group” value.
  • A valid string can start with either a block of 0’s or a block of 1’s.
  • We use dynamic programming with two states: one for strings ending in 0 and one for strings ending in 1.
  • The recurrence for dp0 (ending with 0) uses contributions from dp1 values that are exactly oneGroup apart (since adding a new block of zeros must come after a block of ones) and vice‐versa.
  • To avoid an O(n^2) solution (which is too slow when maxLength is 10^5), we use prefix–sum data structures, but grouped by residue classes modulo oneGroup (or zeroGroup) so that the summations over indices in arithmetic progression can be performed in O(log n) time per query.

Space and Time Complexity

Time Complexity: O(maxLength · log(maxLength)) worst-case (when oneGroup or zeroGroup are small) due to binary searches over the residue–classes. Space Complexity: O(maxLength), to store the dp arrays and the precomputed cumulative sums for each residue.

Solution

We solve the problem by doing dynamic programming over the length of the string. We maintain two arrays: • dp0[i]: number of valid strings of length i that end with a block of 0’s. • dp1[i]: number of valid strings of length i that end with a block of 1’s.

For each valid ending, the recurrence is as follows. For instance, if a valid string ending with 0 is formed by appending a block of 0’s (whose length L is a positive multiple of zeroGroup) to a valid string that ended with 1 – or directly starting the string – then

  dp0[i] = (if i is a positive multiple of zeroGroup, add the “base” case) + Sum(dp1[i – m * oneGroup]) for all m such that i – m * oneGroup ≥ 0.

Similarly,   dp1[i] = (if i is a positive multiple of oneGroup, add the “base” case) + Sum(dp0[i – m * zeroGroup]) for all m such that i – m * zeroGroup ≥ 0.

Because the summations are over indices that form an arithmetic progression (the difference between indices is oneGroup for dp0’s recurrence and zeroGroup for dp1’s), we can precompute and maintain cumulative sums keyed by the residue modulo oneGroup (or zeroGroup). In our implementation the idea is to store, for each residue class, the dp values along with a prefix–sum so that for each new index i we can quickly query the cumulative contribution from indices j that are congruent to i modulo oneGroup (if computing dp0) and up to i – oneGroup. (A similar idea applies when computing dp1.)

Finally, the answer is the total number of valid strings (dp0[i] + dp1[i]) for each i in [minLength, maxLength], taken modulo 10^9+7.

Important implementation details include ensuring that the “base” (i.e. a single block) is counted correctly, and taking the modulo at each step to avoid overflow.

Code Solutions

# Python solution using DP and precomputed prefix sums by residue.
MOD = 10**9 + 7

def numberOfGoodBinaryStrings(minLength, maxLength, oneGroup, zeroGroup):
    dp0 = [0] * (maxLength + 1)  # dp0[i]: valid strings of length i ending with 0.
    dp1 = [0] * (maxLength + 1)  # dp1[i]: valid strings of length i ending with 1.
    
    # For efficient queries over indices that are in arithmetic progression, we store lists for each residue.
    # For dp1 queries (needed when computing dp0) we group indices by residue modulo oneGroup.
    dp1_by_res = {r: [] for r in range(oneGroup)}
    ind1_by_res = {r: [] for r in range(oneGroup)}  # indices corresponding to dp1 values for each residue.
    # Similarly for dp0 queries when computing dp1
    dp0_by_res = {r: [] for r in range(zeroGroup)}
    ind0_by_res = {r: [] for r in range(zeroGroup)}
    
    # Helper: binary search in the list for the rightmost index with value <= x
    def bs(prefix_list, x):
        # prefix_list is a list of (index, cumulative sum)
        lo, hi = 0, len(prefix_list) - 1
        best = -1
        while lo <= hi:
            mid = (lo + hi) // 2
            if prefix_list[mid][0] <= x:
                best = mid
                lo = mid + 1
            else:
                hi = mid - 1
        return best
    
    # We will keep cumulative prefix sums for each residue as a list of tuples: (i, cum_sum).
    # Initially they are empty; we update them after computing dp1[i] or dp0[i].
    prefix_dp1 = {r: [] for r in range(oneGroup)}
    prefix_dp0 = {r: [] for r in range(zeroGroup)}
    
    # Function to update prefix list for a given residue.
    def update_prefix(prefix_dict, r, i, value):
        if prefix_dict[r]:
            cum = (prefix_dict[r][-1][1] + value) % MOD
        else:
            cum = value % MOD
        prefix_dict[r].append((i, cum))
            
    # The recurrences:
    for i in range(1, maxLength + 1):
        # Compute dp0[i]: Ending with a block of 0's.
        # Base: if i is a multiple of zeroGroup then we can form a valid string starting with a block of zeros.
        base0 = 1 if i % zeroGroup == 0 else 0
        add_from_dp1 = 0
        # We want to sum dp1[j] for j = i - m * oneGroup (m>=1) and j >= 0.
        if i - oneGroup >= 0:
            r = i % oneGroup  # j must have the same residue as i.
            if prefix_dp1[r]:
                # We need to include only those indices j <= i - oneGroup.
                pos = bs(prefix_dp1[r], i - oneGroup)
                if pos != -1:
                    add_from_dp1 = prefix_dp1[r][pos][1]
        dp0[i] = (base0 + add_from_dp1) % MOD
        
        # After computing dp0[i], update the prefix for dp0 queries (for dp1 computation later).
        r0 = i % zeroGroup
        update_prefix(prefix_dp0, r0, i, dp0[i])
        
        # Now compute dp1[i]: Ending with a block of 1's.
        base1 = 1 if i % oneGroup == 0 else 0
        add_from_dp0 = 0
        if i - zeroGroup >= 0:
            r = i % zeroGroup  # For dp0 indices.
            if prefix_dp0[r]:
                pos = bs(prefix_dp0[r], i - zeroGroup)
                if pos != -1:
                    add_from_dp0 = prefix_dp0[r][pos][1]
        dp1[i] = (base1 + add_from_dp0) % MOD
        
        # Update the prefix for dp1 queries.
        r1 = i % oneGroup
        update_prefix(prefix_dp1, r1, i, dp1[i])
        
    # Sum dp0 and dp1 for lengths in [minLength, maxLength]
    result = 0
    for i in range(minLength, maxLength + 1):
        result = (result + dp0[i] + dp1[i]) % MOD
    return result

# Example usage:
print(numberOfGoodBinaryStrings(2, 3, 1, 2))  # Expected output: 5
print(numberOfGoodBinaryStrings(4, 4, 4, 3))  # Expected output: 1
← Back to All Questions