Number of Substrings With Fixed Ratio solution and explanation
The problem
You are given a binary string s, and two integers num1 and num2. num1 and num2 are coprime numbers.
A ratio substring is a substring of s where the ratio between the number of 0's and the number of 1's in the substring is exactly num1 : num2.
- For example, if
num1 = 2andnum2 = 3, then"01011"and"1110000111"are ratio substrings, while"11000"is not.
Return the number of non-empty ratio substrings of s.
Note that:
- A substring is a contiguous sequence of characters within a string.
- Two values
xandyare coprime ifgcd(x, y) == 1wheregcd(x, y)is the greatest common divisor ofxandy.
Example 1:
Input: s = "0110011", num1 = 1, num2 = 2 Output: 4 Explanation: There exist 4 non-empty ratio substrings. - The substring s[0..2]: "0110011". It contains one 0 and two 1's. The ratio is 1 : 2. - The substring s[1..4]: "0110011". It contains one 0 and two 1's. The ratio is 1 : 2. - The substring s[4..6]: "0110011". It contains one 0 and two 1's. The ratio is 1 : 2. - The substring s[1..6]: "0110011". It contains two 0's and four 1's. The ratio is 2 : 4 == 1 : 2. It can be shown that there are no more ratio substrings.
Example 2:
Input: s = "10101", num1 = 3, num2 = 1 Output: 0 Explanation: There is no ratio substrings of s. We return 0.
Constraints:
1 <= s.length <= 1051 <= num1, num2 <= s.lengthnum1andnum2are coprime integers.
Approach overview
Problem Overview: Given a binary string s and integers num1 and num2, count substrings where the number of 0s and 1s follow the ratio num1 : num2. A substring is valid when zeros * num2 == ones * num1.
Approach 1: Brute Force Substring Enumeration (O(n²) time, O(1) space)
Iterate over every possible starting index and extend the substring one character at a time. Maintain running counts of zeros and ones while expanding the window. For each extension, check whether zeros * num2 == ones * num1. This approach directly follows the problem definition and helps confirm the ratio condition logic. The downside is quadratic time because every substring is evaluated, which becomes too slow for large strings.
Approach 2: Prefix Sum + Hash Counting (O(n) time, O(n) space)
Track cumulative counts of zeros and ones while scanning the string once. Rearrange the ratio condition zeros * num2 == ones * num1 into a prefix form: zeros * num2 - ones * num1. If two prefix states produce the same value, the substring between them satisfies the required ratio. Store the frequency of each computed value in a hash map and increment the result whenever the same value appears again. This converts the substring problem into a prefix matching problem similar to many prefix sum techniques.
The key insight: identical values of zeros * num2 - ones * num1 indicate that the difference between two prefixes cancels out, meaning the substring between them has the exact ratio. Hash lookups allow constant-time counting of previous occurrences, which makes the algorithm linear.
This solution combines ideas from hash table frequency counting and prefix transformations over a string. The same pattern appears in problems involving equal counts, balanced substrings, or fixed relationships between characters.
Recommended for interviews: The Prefix Sum + Hash Counting approach is the expected solution. Interviewers want to see how you transform a ratio constraint into a prefix invariant and use a hash map to count matches efficiently. Mentioning the brute force approach first shows you understand the problem baseline, but deriving the prefix transformation demonstrates stronger algorithmic insight.
Solution
We use one[i] to represent the number of 1s in the substring s[0,..i], and zero[i] to represent the number of 0s in the substring s[0,..i]. A substring meets the condition if
$
\frac{zero[j] - zero[i]}{one[j] - one[i]} = \frac{num1}{num2}
where i < j. We can transform the above equation into
one[j] times num1 - zero[j] times num2 = one[i] times num1 - zero[i] times num2
When we iterate to index j, we only need to count how many indices i satisfy the above equation. Therefore, we can use a hash table to record the number of occurrences of one[i] times num1 - zero[i] times num2, and when we iterate to index j, we only need to count the number of occurrences of one[j] times num1 - zero[j] times num2.
The hash table initially only has one key-value pair (0, 1).
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the string s$.
class Solution:
def fixedRatio(self, s: str, num1: int, num2: int) -> int:
n0 = n1 = 0
ans = 0
cnt = Counter({0: 1})
for c in s:
n0 += c == '0'
n1 += c == '1'
x = n1 * num1 - n0 * num2
ans += cnt[x]
cnt[x] += 1
return ansclass Solution {
public long fixedRatio(String s, int num1, int num2) {
long n0 = 0, n1 = 0;
long ans = 0;
Map<Long, Long> cnt = new HashMap<>();
cnt.put(0L, 1L);
for (char c : s.toCharArray()) {
n0 += c == '0' ? 1 : 0;
n1 += c == '1' ? 1 : 0;
long x = n1 * num1 - n0 * num2;
ans += cnt.getOrDefault(x, 0L);
cnt.put(x, cnt.getOrDefault(x, 0L) + 1);
}
return ans;
}
}using ll = long long;
class Solution {
public:
long long fixedRatio(string s, int num1, int num2) {
ll n0 = 0, n1 = 0;
ll ans = 0;
unordered_map<ll, ll> cnt;
cnt[0] = 1;
for (char& c : s) {
n0 += c == '0';
n1 += c == '1';
ll x = n1 * num1 - n0 * num2;
ans += cnt[x];
++cnt[x];
}
return ans;
}
};func fixedRatio(s string, num1 int, num2 int) int64 {
n0, n1 := 0, 0
ans := 0
cnt := map[int]int{0: 1}
for _, c := range s {
if c == '0' {
n0++
} else {
n1++
}
x := n1*num1 - n0*num2
ans += cnt[x]
cnt[x]++
}
return int64(ans)
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Enumeration | O(n²) | O(1) | Useful for understanding the ratio condition or when constraints are very small. |
| Prefix Sum + Hash Counting | O(n) | O(n) | Best general solution for large inputs. Converts the ratio condition into a prefix invariant and counts matches using a hash map. |
Frequently asked questions
Is Number of Substrings With Fixed Ratio easy or hard?
This problem is typically rated Medium. The main challenge is recognizing how to convert the ratio condition into a prefix invariant and apply hash map counting. Once the transformation zeros * num2 - ones * num1 is identified, the implementation becomes straightforward.
Number of Substrings With Fixed Ratio Python/Java solution
Implement the prefix sum + hash map technique. Maintain counts of zeros and ones while iterating through the string, compute zeros * num2 - ones * num1, and track its frequency in a map. The same logic works across Python, Java, C++, and Go with O(n) time complexity.
How to solve Number of Substrings With Fixed Ratio in O(n)?
Track cumulative counts of zeros and ones while iterating through the string. Convert the ratio condition into a prefix expression: zeros * num2 - ones * num1. Store frequencies of this value in a hash map and add the previous count whenever it reappears. Matching prefix values indicate substrings that satisfy the ratio constraint.
What is the best approach for Number of Substrings With Fixed Ratio?
The most efficient method uses a prefix sum transformation combined with a hash map. While scanning the string, compute the value zeros * num2 - ones * num1 and store its frequency. Whenever the same value appears again, it indicates a valid substring between the two prefixes. This approach runs in O(n) time and O(n) space.
Is Number of Substrings With Fixed Ratio asked at Google/Amazon/Meta?
Problems involving prefix sums and hash map frequency counting are common in interviews at companies like Amazon, Google, and Meta. Variants that count substrings with specific relationships between characters appear frequently in coding interviews and online assessments.
What data structure is used in Number of Substrings With Fixed Ratio?
The core data structure is a hash map (dictionary) that stores frequencies of transformed prefix values. The algorithm also relies on prefix counting of zeros and ones in the string to evaluate the ratio condition efficiently.
What is the time complexity of Number of Substrings With Fixed Ratio?
The optimal solution runs in O(n) time where n is the length of the string. Each character is processed once while updating prefix counts and performing constant‑time hash map lookups. The space complexity is O(n) due to storing prefix state frequencies.