2489. Number of Substrings With Fixed Ratio

Problem Description

The problem provides us with a binary string s and two integers num1 and num2 that are coprime (meaning their greatest common divisor is 1). We are tasked with finding the number of non-empty substrings (contiguous sequence of characters within the string) where the ratio of the number of 0s to the number of 1s is exactly num1 : num2.

To illustrate, if num1 = 2 and num2 = 3, a valid ratio substring might be "01011" since there are two 0s and three 1s. The problem requires us to count all such substrings in the given binary string s.

Intuition

The solution leverages the fact that the difference between num1 times the count of 1s and num2 times the count of 0s in a substring will be the same for all substrings that have the num1 : num2 ratio. To keep track of these differences, a counter is used while iterating through the string.

Here's how we arrive at the solution step by step:

1. Initialize two counters, n0 and n1, to count the number of 0s and 1s encountered in the string as we iterate.
2. Use a counter dictionary, cnt, to keep track of how many times each difference (key) has occurred, starting with a difference of 0 occurring once ({0: 1}).
3. Iterate through the string, updating n0 and n1 each time we encounter a 0 or 1, respectively.
4. Calculate the current difference x = n1 * num1 - n0 * num2. This difference will be the same for all substrings that satisfy the ratio condition.
5. Increment the answer by the count of how many times we've encountered this difference previously, because each occurrence indicates a potential starting point for a valid substring ending at the current position.
6. Update the counter for the current difference, indicating that we have another potential starting point for future substrings.
7. At the end of the string, ans contains the total count of ratio substrings.

This approach effectively reduces the problem to a single pass through the string with a constant-time check for each character, making it very efficient.

Solution Approach

For implementing the solution to count the non-empty ratio substrings, a combination of prefix sums, mathematical reasoning, and a hash map to efficiently count differences is used.

Here is the detailed breakdown of the algorithm:

1. Initialize two variables n0 and n1 to count the occurrences of 0s and 1s, respectively, as we iterate through the binary string s.

2. Initialize a variable ans to store the count of valid ratio substrings. This will be our final answer.

3. Create a Counter dictionary cnt to keep track of the observed differences. Start with a difference of 0 that has occurred once. This relates to the empty substring before we start.

4. Iterate through each character c in the string s.

   • When the character is '0', increment n0.
   • When the character is '1', increment n1.

5. For each character in the string, calculate the difference x which is given by the formula x = n1 * num1 - n0 * num2. This will give us a unique value for a valid ratio between num1 : num2 at each position in the string.

6. The value x represents the cumulative difference at any point in the string. Look up this difference in the cnt dictionary. The value associated with this difference is the number of times a substring has ended at the current point in the string with a valid ratio.

7. Add the value from cnt[x] to ans. If the difference x has not been encountered before, it contributes 0 to ans, as seen from the initialization of cnt.

8. Finally, increment the count for the difference x in cnt. This step records that a new potential starting point for valid ratio substrings has been found.

9. After the end of the loop, the ans variable holds the total number of valid ratio substrings found in the binary string s.

We use a hash map (Counter) for fast lookups and updates of the differences, which allows the solution to run with a time complexity of O(n), where n is the length of the binary string. The combination of prefix sums (here, the cumulative counts of 0s and 1s) and the hash map to record the frequencies of differences encountered so far is a powerful pattern that enables us to efficiently solve this problem.

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have a binary string s = "010101" and our coprime numbers num1 = 2 and num2 = 1. This means we want to count substrings where the number of 0s to the number of 1s is exactly 2:1.

Follow along with the following steps:

1. Initialize two variables n0 = 0 and n1 = 0 for counting 0s and 1s as we go along.
2. Initialize ans = 0 which will hold the final count of valid ratio substrings.
3. Create a Counter dict cnt = {0: 1} to keep track of the observed differences, starting with a 0 difference.
4. Start iterating through each character in s.
   • Read first character: c = '0', increment n0 to 1.
   • Calculate difference: x = n1 * 2 - n0 * 1 = 0 * 2 - 1 * 1 = -1.
   • Add cnt[x] to ans: ans = ans + cnt.get(x, 0) = 0 (since -1 is not in cnt, we assume 0).
   • Update cnt with the new difference: cnt[-1] = cnt.get(-1, 0) + 1 = 1.
5. Move to the next character and repeat steps.
   • c = '1', increment n1 to 1.
   • Calculate x = 1 * 2 - 1 * 1 = 1.
   • ans = ans + cnt.get(x, 0) = 0 (since 1 is not in cnt, we assume 0).
   • Update cnt: cnt[1] = cnt.get(1, 0) + 1 = 1.
6. Continue with the rest of the string:
   • Next c = '0'; n0 = 2; x = 1 * 2 - 2 * 1 = 0; ans = ans + cnt[0] = 1; cnt[0] = cnt[0] + 1 = 2.
   • Next c = '1'; n1 = 2; x = 2 * 2 - 2 * 1 = 2; ans = ans + cnt.get(x, 0) = 2; cnt[2] = cnt.get(2, 0) + 1 = 1.
   • Next c = '0'; n0 = 3; x = 2 * 2 - 3 * 1 = 1; ans = ans + cnt[1] = 2; cnt[1] = cnt[1] + 1 = 2.
   • Last c = '1'; n1 = 3; x = 3 * 2 - 3 * 1 = 3; ans = ans + cnt.get(x, 0) = 2 (since 3 is not in cnt, we assume 0); cnt[3] = cnt.get(3, 0) + 1 = 1.
7. After iterating through all characters, ans holds the total count of valid ratio substrings. In this case, ans = 2.

The two valid substrings are "01" from positions 1 to 2 and "0101" from positions 1 to 4. Each time we found the required difference, it indicated that a valid substring ended at the current character, thus we added the count from cnt.

By keeping track of the differences and using them to map to potential substring start points, we've efficiently counted the substrings with ratios of 0s to 1s of 2:1 without needing to check every possible substring explicitly.

Python Solution

1from collections import Counter
2
3class Solution:
4    def fixedRatio(self, string: str, num_zeros: int, num_ones: int) -> int:
5        # Initialize counters for '0's and '1's and result variable ans
6        count_zeros = count_ones = 0
7        ans = 0
8      
9        # Initialize a Counter to keep track of the differences
10        counter = Counter({0: 1})
11      
12        # Iterate over each character in the input string
13        for char in string:
14            # Increment the count of '0's and '1's based on the current character
15            count_zeros += char == '0'
16            count_ones += char == '1'
17          
18            # Calculate the difference between the counts of '1's and '0's multiplied by respective input factors
19            difference = count_ones * num_zeros - count_zeros * num_ones
20          
21            # Accumulate the number of occurrences of the current difference
22            ans += counter[difference]
23          
24            # Increment the count for the current difference in the counter
25            counter[difference] += 1
26      
27        # Return the final accumulated result
28        return ans
29

Java Solution

1import java.util.HashMap;
2import java.util.Map;
3
4class Solution {
5    // Function to calculate the number of substrings with a fixed ratio between the number of '0's and '1's.
6    public long fixedRatio(String s, int num1, int num2) {
7        // Initialize the count of '0's and '1's seen so far.
8        long count0 = 0, count1 = 0;
9        // Initialize the answer, which will store the number of valid substrings.
10        long answer = 0;
11        // HashMap to store the counts of differences computed.
12        Map<Long, Long> countMap = new HashMap<>();
13        // Initially put a difference of '0' with a count of '1' into the map.
14        countMap.put(0L, 1L);
15      
16        // Iterate over each character in the input string.
17        for (char c : s.toCharArray()) {
18            // Increment count0 if the current character is '0'.
19            count0 += c == '0' ? 1 : 0;
20            // Increment count1 if the current character is '1'.
21            count1 += c == '1' ? 1 : 0;
22          
23            // Determine the current difference based on the fixed ratio.
24            long currentDifference = count1 * num1 - count0 * num2;
25            // Increment answer by the count of this difference seen so far.
26            answer += countMap.getOrDefault(currentDifference, 0L);
27            // Update the count of the current difference in the map.
28            countMap.put(currentDifference, countMap.getOrDefault(currentDifference, 0L) + 1);
29        }
30      
31        // Return the total count of valid substrings.
32        return answer;
33    }
34}
35

C++ Solution

1#include <string>
2#include <unordered_map>
3
4// Define a type alias 'll' for 'long long' for convenient usage.
5using ll = long long;
6
7class Solution {
8public:
9    // This function calculates the number of substrings where 
10    // the ratio of the number of '1's to the number of '0's is num1 : num2.
11    long long fixedRatio(const string& s, int num1, int num2) {
12        // Initialize counters for '0's and '1's, and for the answer.
13        ll count0 = 0, count1 = 0;
14        ll answer = 0;
15        // Create a hash map to store the frequency of each ratio difference.
16        unordered_map<ll, ll> frequencyCounter;
17        // Initialize the ratio difference of 0 with a count of 1.
18        frequencyCounter[0] = 1;
19      
20        // Iterate through each character in the string.
21        for (const char& c : s) {
22            // Increment the count for '0's or '1's based on the current character.
23            count0 += (c == '0');
24            count1 += (c == '1');
25          
26            // Calculate the current difference in the scaled counts of '1's and '0's.
27            ll difference = count1 * num1 - count0 * num2;
28          
29            // Increment the answer by the number of times this difference has been seen.
30            answer += frequencyCounter[difference];
31          
32            // Record the current difference by incrementing its count.
33            ++frequencyCounter[difference];
34        }
35        // Return the total count of valid substrings.
36        return answer;
37    }
38};
39

Typescript Solution

1// Importing the necessary module to use the Map data structure.
2import { Map } from "typescript-collections";
3
4// Define an alias 'long' for the 'number' type for long integer simulation.
5type long = number;
6
7// Function to calculate the number of substrings where 
8// the ratio of the number of '1s' to the number of '0s' is num1 : num2.
9function fixedRatio(s: string, num1: number, num2: number): long {
10  // Initialize counters for '0s' and '1s', as well as the answer.
11  let countZeroes: long = 0, countOnes: long = 0;
12  let answer: long = 0;
13
14  // Initialize a map to store the frequency of each ratio difference.
15  let frequencyCounter: Map<long, long> = new Map<long, long>();
16  // Initialize the ratio difference of 0 with a count of 1.
17  frequencyCounter.setValue(0, 1);
18
19  // Iterate over each character in the string.
20  for (const c of s) {
21    // Increment the count for '0s' or '1s' based on the current character.
22    if (c === '0') {
23      countZeroes++;
24    } else {
25      countOnes++;
26    }
27
28    // Calculate the current difference in the scaled counts of '1s' and '0s'.
29    let difference = countOnes * num1 - countZeroes * num2;
30
31    // Get the number of times this difference has been seen,
32    // increment the answer by this amount.
33    let existingFrequency = frequencyCounter.getValue(difference) || 0;
34    answer += existingFrequency;
35
36    // Record the current difference by incrementing its frequency.
37    frequencyCounter.setValue(difference, existingFrequency + 1);
38  }
39
40  // Return the total count of substrings that fulfill the ratio condition.
41  return answer;
42}
43
44// Uncomment the following code to test the functionality
45// let sampleString: string = "0110101";
46// let ratioNum1: number = 2;
47// let ratioNum2: number = 1;
48// console.log(`Number of valid substrings: ${fixedRatio(sampleString, ratioNum1, ratioNum2)}`);
49

Time and Space Complexity

Time Complexity

The given code primarily consists of a single loop that iterates over all characters in the input string s. Inside this loop, the operations performed are constant time operations, including comparison, addition, and dictionary access or update.

• The comparison (c == '0', c == '1'): takes O(1) time each.
• The additions (n0 += ..., n1 += ...): also take O(1) time each.
• The dictionary operations (cnt[x] and cnt[x] += 1): usually take O(1) time, thanks to the hash table implementation of Python dictionaries.

Since these O(1) operations are performed once for each of the n characters in the input string, the overall time complexity is O(n), where n is the length of the string s.

Space Complexity

The space complexity comes from the variables n0, n1, and the Counter dictionary cnt.

• n0 and n1: these are just two integer counters, which use O(1) space.
• cnt: at worst, it will contain a distinct count for every prefix sum difference encountered. In the worst case, each prefix difference is unique, leading to n entries.

Therefore, the worst-case space complexity is O(n), where n is the length of the string s.