Watch 2 video solutions for Number of Substrings With Fixed Ratio, a medium level problem involving Hash Table, Math, String. This walkthrough by Code-Yao has 368 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
num1 = 2 and num2 = 3, then "01011" and "1110000111" are ratio substrings, while "11000" is not.Return the number of non-empty ratio substrings of s.
Note that:
x and y are coprime if gcd(x, y) == 1 where gcd(x, y) is the greatest common divisor of x and y.
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.lengthnum1 and num2 are coprime integers.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.
| 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. |