Problem Description

You are given a binary string s consisting of only '0's and '1's, along with two coprime integers num1 and num2.

A ratio substring is defined as any substring of s where the ratio between the count of '0's and the count of '1's is exactly num1 : num2. This means if a substring has x zeros and y ones, then x/y = num1/num2.

For example, if num1 = 2 and num2 = 3:

• "01011" is a ratio substring because it has 2 zeros and 3 ones (ratio 2:3)
• "1110000111" is a ratio substring because it has 4 zeros and 6 ones (ratio 4:6 = 2:3)
• "11000" is NOT a ratio substring because it has 3 zeros and 2 ones (ratio 3:2 ≠ 2:3)

Your task is to count the total number of non-empty substrings in s that are ratio substrings.

Key points to remember:

• A substring is a contiguous sequence of characters from the string
• Two numbers are coprime if their greatest common divisor (GCD) equals 1
• The substring must be non-empty
• Since num1 and num2 are coprime, the ratio num1:num2 is already in its simplest form

The solution uses a clever transformation: instead of checking each substring individually, it uses the fact that a substring from index i to j satisfies the ratio if zeros[i,j] / ones[i,j] = num1 / num2, which can be rearranged to ones[i,j] * num1 - zeros[i,j] * num2 = 0. Using prefix sums, this becomes (ones[j] - ones[i]) * num1 - (zeros[j] - zeros[i]) * num2 = 0, which simplifies to checking when ones[j] * num1 - zeros[j] * num2 = ones[i] * num1 - zeros[i] * num2.

Intuition

The naive approach would be to check every possible substring and count zeros and ones to verify if they satisfy the ratio num1:num2. However, this would be inefficient with O(n²) substrings to check.

The key insight comes from transforming the ratio condition into something we can track efficiently. For a substring to have the correct ratio, we need: count_of_zeros / count_of_ones = num1 / num2

Cross-multiplying gives us: count_of_zeros * num2 = count_of_ones * num1

Rearranging: count_of_ones * num1 - count_of_zeros * num2 = 0

Now, instead of thinking about individual substrings, we can think about prefix counts. If we track the cumulative count of ones and zeros as we traverse the string, a substring from position i to position j has:

• Ones: ones[j] - ones[i]
• Zeros: zeros[j] - zeros[i]

The ratio condition becomes: (ones[j] - ones[i]) * num1 - (zeros[j] - zeros[i]) * num2 = 0

Expanding this: ones[j] * num1 - zeros[j] * num2 = ones[i] * num1 - zeros[i] * num2

This reveals the crucial pattern: for any position j, we need to find how many previous positions i have the same value of ones * num1 - zeros * num2. This is a classic pattern that can be solved using a hash map to count occurrences of each value.

As we iterate through the string:

1. We maintain running counts of ones and zeros
2. We calculate the value x = ones * num1 - zeros * num2 at each position
3. We check how many times we've seen this value x before (these represent valid starting positions for ratio substrings ending at the current position)
4. We add the current value to our hash map for future positions

The hash map is initialized with {0: 1} to handle substrings that start from the beginning of the string (when both prefix counts are 0).

Learn more about Math and Prefix Sum patterns.

Solution Approach

The solution implements a prefix sum approach combined with hash map counting to efficiently find all ratio substrings.

Data Structures Used:

• Two counters n0 and n1 to track the cumulative count of '0's and '1's respectively
• A hash map cnt (using Python's Counter) to store frequency of transformed values
• An answer counter ans to accumulate the result

Algorithm Steps:

1. Initialize the hash map: Start with cnt = {0: 1}. This handles the case where a valid substring starts from index 0, as the "empty prefix" has a transformed value of 0.

2. Iterate through each character in the string:

   • Update the prefix counts:
     • If current character is '0': increment n0
     • If current character is '1': increment n1

3. Calculate the transformed value: For the current position, compute:

   x = n1 * num1 - n0 * num2

   This represents the value ones * num1 - zeros * num2 at the current prefix.

4. Count valid substrings ending at current position:

   • Look up cnt[x] - this tells us how many previous positions have the same transformed value
   • Add this count to ans because each such position forms a valid ratio substring when paired with the current position

5. Update the hash map: Increment cnt[x] by 1 to record that we've seen this transformed value one more time (at the current position).

Why this works:

• When two positions i and j have the same transformed value (ones[i] * num1 - zeros[i] * num2 = ones[j] * num1 - zeros[j] * num2), the substring between them has exactly the ratio num1:num2
• By maintaining the count of each transformed value seen so far, we can immediately determine how many valid substrings end at each position
• The total time complexity is O(n) where n is the length of the string, as we make a single pass through the string with O(1) operations at each step
• Space complexity is O(n) in the worst case for the hash map

The elegance of this solution lies in transforming a ratio comparison problem into a difference problem, allowing us to use the common pattern of "finding subarrays with a specific sum" (here, sum of 0 after transformation).

Example Walkthrough

Let's walk through a concrete example with s = "0101", num1 = 1, and num2 = 2.

We want to find substrings where the ratio of zeros to ones is 1:2 (meaning for every 1 zero, there should be 2 ones).

Step-by-step execution:

Initial state:

• n0 = 0 (count of zeros)
• n1 = 0 (count of ones)
• cnt = {0: 1} (hash map initialized with 0)
• ans = 0 (answer counter)

Position 0: s[0] = '0'

• Update counts: n0 = 1, n1 = 0
• Calculate transformed value: x = n1 * num1 - n0 * num2 = 0 * 1 - 1 * 2 = -2
• Check cnt[-2]: Not found, so 0 valid substrings end here
• Update hash map: cnt = {0: 1, -2: 1}
• ans = 0

Position 1: s[1] = '1'

• Update counts: n0 = 1, n1 = 1
• Calculate transformed value: x = 1 * 1 - 1 * 2 = -1
• Check cnt[-1]: Not found, so 0 valid substrings end here
• Update hash map: cnt = {0: 1, -2: 1, -1: 1}
• ans = 0

Position 2: s[2] = '0'

• Update counts: n0 = 2, n1 = 1
• Calculate transformed value: x = 1 * 1 - 2 * 2 = -3
• Check cnt[-3]: Not found, so 0 valid substrings end here
• Update hash map: cnt = {0: 1, -2: 1, -1: 1, -3: 1}
• ans = 0

Position 3: s[3] = '1'

• Update counts: n0 = 2, n1 = 2
• Calculate transformed value: x = 2 * 1 - 2 * 2 = -2
• Check cnt[-2]: Found with value 1! This means there's 1 position (after position 0) with the same transformed value
  • This corresponds to the substring from position 1 to 3: "101" which has 1 zero and 2 ones (ratio 1:2 ✓)
• Update ans = 0 + 1 = 1
• Update hash map: cnt = {0: 1, -2: 2, -1: 1, -3: 1}

Final answer: 1

Verification: Let's verify by checking all possible substrings:

• "0" → 1 zero, 0 ones (invalid - division by zero)
• "01" → 1 zero, 1 one (ratio 1:1 ≠ 1:2)
• "010" → 2 zeros, 1 one (ratio 2:1 ≠ 1:2)
• "0101" → 2 zeros, 2 ones (ratio 2:2 = 1:1 ≠ 1:2)
• "1" → 0 zeros, 1 one (ratio 0:1 ≠ 1:2)
• "10" → 1 zero, 1 one (ratio 1:1 ≠ 1:2)
• "101" → 1 zero, 2 ones (ratio 1:2 ✓)
• "0" → 1 zero, 0 ones (invalid)
• "01" → 1 zero, 1 one (ratio 1:1 ≠ 1:2)
• "1" → 0 zeros, 1 one (ratio 0:1 ≠ 1:2)

Indeed, only "101" satisfies the ratio requirement, confirming our answer of 1.

The key insight is that when we found x = -2 at position 3, it matched the value from position 0, indicating that the substring between these positions (exclusive of position 0, inclusive of position 3) maintains the required ratio.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. The algorithm iterates through each character in the string exactly once. Within each iteration, all operations are constant time: incrementing counters (n0 and n1), computing the value x = n1 * num1 - n0 * num2, accessing and updating the Counter dictionary, and adding to ans. Dictionary operations (lookup and insertion) are O(1) on average.

The space complexity is O(n), where n is the length of the string s. The Counter dictionary cnt stores at most n + 1 distinct values (one for the initial state and potentially one unique value for each character position). In the worst case, each prefix of the string could produce a different value of x = n1 * num1 - n0 * num2, resulting in n + 1 entries in the dictionary. All other variables (n0, n1, ans, x) use constant space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Ratio Interpretation

A critical pitfall is misunderstanding which count corresponds to which parameter. The problem states the ratio is zeros:ones = num1:num2, but developers often reverse this relationship.

Wrong interpretation:

# Incorrectly assuming num1 corresponds to ones and num2 to zeros
weighted_difference = zeros_count * num1 - ones_count * num2

Correct interpretation:

# num1 corresponds to zeros, num2 corresponds to ones
# So zeros/ones = num1/num2, which rearranges to:
weighted_difference = zeros_count * num2 - ones_count * num1

2. Forgetting to Initialize the Hash Map with {0: 1}

The hash map must be initialized with {0: 1} to handle substrings that start from the beginning of the string. Without this, valid substrings starting at index 0 won't be counted.

Incorrect:

difference_frequency = Counter()  # Missing initial value

Correct:

difference_frequency = Counter({0: 1})  # Handles empty prefix

3. Order of Operations: Counting Before Updating

The order matters - you must first add the count of previous occurrences to the result, then update the frequency map. Reversing this order will incorrectly include the current position in its own count.

Wrong order:

# Updates frequency first (incorrect)
difference_frequency[weighted_difference] += 1
result += difference_frequency[weighted_difference]  # Now includes current position

Correct order:

# Count previous occurrences first
result += difference_frequency[weighted_difference]
# Then update for future positions
difference_frequency[weighted_difference] += 1

4. Edge Case: All Zeros or All Ones

When the string contains only zeros or only ones, the ratio check becomes problematic. For instance, if s = "0000" and we're looking for ratio 2:3, no valid substring exists since there are no ones. The algorithm handles this correctly, but developers might add unnecessary special case handling that introduces bugs.

5. Integer Overflow in Other Languages

While Python handles arbitrary precision integers automatically, implementing this in languages like Java or C++ requires careful consideration of potential overflow when calculating ones_count * num1 - zeros_count * num2 for large strings and large ratio values.

Solution for languages with fixed integer sizes:

// Use long instead of int to prevent overflow
long weightedDifference = (long)onesCount * num1 - (long)zerosCount * num2;