Count Number of Substrings With Fixed Ratio
Given a binary string s and two coprime integers n1 and n2, the task is to find the number of non-empty substrings where the ratio of 0’s to 1’s is exactly n1 : n2.
Example:
Input: s = “0110011”, n1 = 1, n2 = 2
Output: 4
Explanation: There are 4 non-empty substrings with the ratio of the number of 0’s to the number of 1’s equal to 1:2.
- The substring “0110011″ from index 0 to 2 has 1 ‘0’ and 2 ‘1’s, with a ratio of 1:2.
- The substring “0110011″ from index 1 to 4 has 1 ‘0’ and 2 ‘1’s, with a ratio of 1:2.
- The substring “0110011” from index 4 to 6 has 1 ‘0’ and 2 ‘1’s, with a ratio of 1:2.
- The substring “0110011″ from index 1 to 6 has 2 ‘0’s and 4 ‘1’s, with a ratio of 1:2. There are no other such substrings, so the answer is 4.
Input: s = “10101”, n1 = 3, n2 = 1
Output: 0
Explanation: There are no substrings with the ratio of the number of ‘0’s to the number of ‘1’s equal to 3:1, so the answer is 0.
Approach: To solve the problem, follow the below idea:
The main idea is that this ratio can be expressed as an equation: (number of 0s in the substring) / (number of 1s in the substring) = n1 / n2.
Let’s assume the count of 0s till any index i is C0 and count of 1s till index i be C1. Then for any other index j (j < i), let the count of 0s till j be C2 and count of 1s till j be C3. Now, the number of 0s and 1s in substring from index j to i should be in the ration of n1:n2. This gives us,
(C0 – C2) / (C1 – C3) = n1/n2 … (1)
On resolving the above equation, we get
n2 * C0 – n1 * C1 = n2 * C2 – n1 * C3 … (2)
We can store the value of above equation at each index and then check how many indices before the current index has the same value for the above equation.
Steps-by-step approach:
- Initialize variables:
- result: Stores the count of valid substrings (initialized to 0).
- count: Stores the count of 0s and 1s encountered so far (initialized to [0, 0]).
- prefix_sum: Stores the prefix sum of (n2 * count[0] – n1 * count[1]) for each index (initialized to a vector of 0s with length equal to the string length).
- Calculate prefix sums:
- Iterate through the string s:
- Increment the count of 0s or 1s based on the current character.
- Calculate the prefix sum for the current index and store it in prefix_sum.
- Iterate through the string s:
- Use frequency map:
- Initialize a dictionary freq to store the frequency of each prefix sum encountered. Set the initial value for key 0 to 1 to handle substrings starting from the beginning.
- Count valid substrings:
- Iterate through the string s again:
- Check if the current prefix sum is present in the freq dictionary.
- If yes, increment the result by the frequency of the prefix sum.
- Update the frequency of the current prefix sum in the dictionary.
- Iterate through the string s again:
- Return result:
- Return the result, which represents the total number of valid substrings with the desired ratio.
Below is the implementation of the above approach:
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
long long fixedRatio(string s, int n1, int n2)
{
long long result = 0;
// Initialize a vector to store the count of 0s and 1s
// encountered so far.
vector<int> count(2, 0);
// Initialize a vector to store the prefix sum of (n2
// * count[0] - n1 * count[1]) for each index.
int len = s.length();
vector<long long> prefix_sum(len, 0);
// Calculate the prefix sum for each index.
for (int i = 0; i < len; ++i) {
++count[s[i] - '0'];
prefix_sum[i]
= n2 * 1ll * count[0] - n1 * 1ll * count[1];
}
// Use a dictionary to store the frequency of each
// prefix sum encountered. Initialize with 0 to handle
// substrings starting from the beginning.
unordered_map<long long, int> freq = { { 0, 1 } };
// Iterate through the string and count valid
// substrings.
for (int i = 0; i < len; ++i) {
long long key = prefix_sum[i];
if (freq.count(key)) {
result += freq[key];
}
freq[key] = freq[key] + 1;
}
return result;
}
int main()
{
string s = "0110011";
int n1 = 1;
int n2 = 2;
long long result = fixedRatio(s, n1, n2);
cout << "Number of substrings with ratio " << n1 << ":" << n2 << ": " << result << endl;
return 0;
}
import java.util.HashMap;
import java.util.Map;
public class SubstringRatio {
public static long fixedRatio(String s, int n1, int n2)
{
long result = 0;
// Initialize an array to store the count of 0s and
// 1s encountered so far.
int[] count = new int[2];
// Initialize an array to store the prefix sum of
// (n2 * count[0] - n1 * count[1]) for each index.
int len = s.length();
long[] prefixSum = new long[len];
// Calculate the prefix sum for each index.
for (int i = 0; i < len; ++i) {
++count[s.charAt(i) - '0'];
prefixSum[i]
= (long)n2 * count[0] - (long)n1 * count[1];
}
// Use a map to store the frequency of each prefix
// sum encountered. Initialize with 0 to handle
// substrings starting from the beginning.
Map<Long, Integer> freq = new HashMap<>();
freq.put(0L, 1);
// Iterate through the string and count valid
// substrings.
for (int i = 0; i < len; ++i) {
long key = prefixSum[i];
if (freq.containsKey(key)) {
result += freq.get(key);
}
freq.put(key, freq.getOrDefault(key, 0) + 1);
}
return result;
}
public static void main(String[] args)
{
String s = "0110011";
int n1 = 1;
int n2 = 2;
long result = fixedRatio(s, n1, n2);
System.out.println(
"Number of substrings with ratio " + n1 + ":"
+ n2 + ": " + result);
}
}
// This code is contributed by Shivam
def fixed_ratio(s, n1, n2):
result = 0
# Initialize an array to store the count of 0s and
# 1s encountered so far.
count = [0, 0]
# Initialize an array to store the prefix sum of
# (n2 * count[0] - n1 * count[1]) for each index.
len_s = len(s)
prefix_sum = [0] * len_s
# Calculate the prefix sum for each index.
for i in range(len_s):
count[int(s[i])] += 1
prefix_sum[i] = n2 * count[0] - n1 * count[1]
# Use a dictionary to store the frequency of each prefix
# sum encountered. Initialize with 0 to handle
# substrings starting from the beginning.
freq = {0: 1}
# Iterate through the string and count valid
# substrings.
for i in range(len_s):
key = prefix_sum[i]
if key in freq:
result += freq[key]
freq[key] = freq.get(key, 0) + 1
return result
def main():
s = "0110011"
n1 = 1
n2 = 2
result = fixed_ratio(s, n1, n2)
print(f"Number of substrings with ratio {n1}:{n2}: {result}")
if __name__ == "__main__":
main()
function fixedRatio(s, n1, n2) {
let result = 0;
// Initialize an array to store the count of 0s and
// 1s encountered so far.
let count = [0, 0];
// Initialize an array to store the prefix sum of
// (n2 * count[0] - n1 * count[1]) for each index.
const len = s.length;
let prefixSum = new Array(len);
// Calculate the prefix sum for each index.
for (let i = 0; i < len; ++i) {
++count[s.charAt(i) - '0'];
prefixSum[i] = n2 * count[0] - n1 * count[1];
}
// Use a map to store the frequency of each prefix
// sum encountered. Initialize with 0 to handle
// substrings starting from the beginning.
let freq = new Map();
freq.set(0, 1);
// Iterate through the string and count valid
// substrings.
for (let i = 0; i < len; ++i) {
let key = prefixSum[i];
if (freq.has(key)) {
result += freq.get(key);
}
freq.set(key, (freq.get(key) || 0) + 1);
}
return result;
}
function main() {
let s = "0110011";
let n1 = 1;
let n2 = 2;
let result = fixedRatio(s, n1, n2);
console.log(`Number of substrings with ratio ${n1}:${n2}: ${result}`);
}
// Call the main function to execute the code
main();
Output
Number of substrings with ratio 1:2: 4
Time complexity: O(n)
Auxiliary Space: O(n)