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.
Learn more about Math and Prefix Sum patterns.
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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.
Solution Implementation
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
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
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
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
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used to implement priority queue?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we