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 0
s to the number of 1
s is exactly num1 : num2
.
To illustrate, if num1 = 2
and num2 = 3
, a valid ratio substring might be "01011"
since there are two 0
s and three 1
s. 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 1
s and num2
times the count of 0
s 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:
- Initialize two counters,
n0
andn1
, to count the number of0
s and1
s encountered in the string as we iterate. - 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}
). - Iterate through the string, updating
n0
andn1
each time we encounter a0
or1
, respectively. - Calculate the current difference
x = n1 * num1 - n0 * num2
. This difference will be the same for all substrings that satisfy the ratio condition. - 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.
- Update the counter for the current difference, indicating that we have another potential starting point for future substrings.
- 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:
-
Initialize two variables
n0
andn1
to count the occurrences of0
s and1
s, respectively, as we iterate through the binary strings
. -
Initialize a variable
ans
to store the count of valid ratio substrings. This will be our final answer. -
Create a
Counter
dictionarycnt
to keep track of the observed differences. Start with a difference of0
that has occurred once. This relates to the empty substring before we start. -
Iterate through each character
c
in the strings
.- When the character is
'0'
, incrementn0
. - When the character is
'1'
, incrementn1
.
- When the character is
-
For each character in the string, calculate the difference
x
which is given by the formulax = n1 * num1 - n0 * num2
. This will give us a unique value for a valid ratio betweennum1 : num2
at each position in the string. -
The value
x
represents the cumulative difference at any point in the string. Look up this difference in thecnt
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. -
Add the value from
cnt[x]
toans
. If the differencex
has not been encountered before, it contributes0
toans
, as seen from the initialization ofcnt
. -
Finally, increment the count for the difference
x
incnt
. This step records that a new potential starting point for valid ratio substrings has been found. -
After the end of the loop, the
ans
variable holds the total number of valid ratio substrings found in the binary strings
.
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 0
s and 1
s) 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 0
s to the number of 1
s is exactly 2:1
.
Follow along with the following steps:
- Initialize two variables
n0 = 0
andn1 = 0
for counting0
s and1
s as we go along. - Initialize
ans = 0
which will hold the final count of valid ratio substrings. - Create a Counter dict
cnt = {0: 1}
to keep track of the observed differences, starting with a0
difference. - Start iterating through each character in
s
.- Read first character:
c = '0'
, incrementn0
to1
. - Calculate difference:
x = n1 * 2 - n0 * 1 = 0 * 2 - 1 * 1 = -1
. - Add
cnt[x]
toans
:ans = ans + cnt.get(x, 0) = 0
(since-1
is not incnt
, we assume 0). - Update
cnt
with the new difference:cnt[-1] = cnt.get(-1, 0) + 1 = 1
.
- Read first character:
- Move to the next character and repeat steps.
c = '1'
, incrementn1
to1
.- Calculate
x = 1 * 2 - 1 * 1 = 1
. ans = ans + cnt.get(x, 0) = 0
(since1
is not incnt
, we assume 0).- Update
cnt
:cnt[1] = cnt.get(1, 0) + 1 = 1
.
- 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
(since3
is not incnt
, we assume 0);cnt[3] = cnt.get(3, 0) + 1 = 1
.
- Next
- 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 0
s to 1
s 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'
): takesO(1)
time each. - The additions (
n0 += ...
,n1 += ...
): also takeO(1)
time each. - The dictionary operations (
cnt[x]
andcnt[x] += 1
): usually takeO(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
andn1
: these are just two integer counters, which useO(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 ton
entries.
Therefore, the worst-case space complexity is O(n)
, where n
is the length of the string s
.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.