Skip to main content
Talentd

Number of Substrings With Fixed Ratio - Solution & Explanation

MediumPremiumFree on FleetCodeHash TableMathStringPrefix Sum8 min readAsked at: Intuit
Practice this problem

Problem Statement

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 = 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:

  • A substring is a contiguous sequence of characters within a string.
  • Two values 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 <= 105
  • 1 <= num1, num2 <= s.length
  • num1 and num2 are 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$.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Substring EnumerationO(n²)O(1)Useful for understanding the ratio condition or when constraints are very small.
Prefix Sum + Hash CountingO(n)O(n)Best general solution for large inputs. Converts the ratio condition into a prefix invariant and counts matches using a hash map.

Video Solution

leetcode 2489. Number of Substrings With Fixed Ratio - dict and check • Code-Yao • 372 views views

Watch 1 more video solutions →

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.

Ready to solve this problem?

Practice Number of Substrings With Fixed Ratio with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Binary Substrings