LeetCode 2489 - Number of Substrings With Fixed Ratio

LeetCode Problem 2489

Difficulty: 🟡 Medium
Topics: Hash Table, Math, String, Prefix Sum

Solution

Problem Understanding

The problem gives us a binary string s, along with two coprime integers num1 and num2. We need to count how many non-empty substrings contain 0s and 1s in the exact ratio num1 : num2.

If a substring contains:

• zeroCount zeros
• oneCount ones

then it is valid only if:

$$\frac{zeroCount}{oneCount} = \frac{num1}{num2}$$

Because the two numbers are coprime, this condition is equivalent to:

$$zeroCount \times num2 = oneCount \times num1$$

The input size can be as large as 10^5, which immediately tells us that checking every substring explicitly will be too slow. There are O(n^2) substrings in a string of length n, and iterating through all of them would exceed time limits.

The output should be the total number of substrings satisfying the required ratio.

Several edge cases are important:

• A string may contain only 0s or only 1s.
• There may be no valid substrings at all.
• Many substrings may share the same ratio.
• The valid ratio may require large counts, such as 3:5 or 7:2.
• Since the answer can be large, we must use a 64-bit integer type in Go.

The key challenge is finding a way to count valid substrings efficiently without enumerating every possible substring.

Approaches

Brute Force Approach

The most direct solution is to examine every substring.

For each starting index i, we expand the substring one character at a time toward the right. While expanding, we maintain:

• the number of zeros
• the number of ones

At every step, we check whether:

$$zeroCount \times num2 = oneCount \times num1$$

If the equality holds, we increment the answer.

This approach is correct because every substring is checked exactly once, so no valid substring can be missed.

However, there are O(n^2) substrings, and each substring update still requires processing characters. Even with incremental counting, the overall complexity remains quadratic.

For n = 10^5, this is far too slow.

Optimal Prefix Sum + Hash Map Approach

The key observation is that substring ratio conditions can often be transformed into prefix relationships.

Suppose:

• zeros[i] is the number of zeros in the prefix ending before index i
• ones[i] is the number of ones in the prefix ending before index i

For a substring from l to r:

$$substringZeros = zeros[r+1] - zeros[l]$$

$$substringOnes = ones[r+1] - ones[l]$$

The substring is valid if:

$$(substringZeros) \times num2 = (substringOnes) \times num1$$

Substituting prefix sums:

$$(zeros[r+1] - zeros[l]) \times num2 = (ones[r+1] - ones[l]) \times num1$$

Rearranging:

$$zeros[r+1] \times num2 - ones[r+1] \times num1 = zeros[l] \times num2 - ones[l] \times num1$$

This is the crucial insight.

If two prefixes produce the same value of:

$$zeros \times num2 - ones \times num1$$

then the substring between them has the required ratio.

So instead of checking substrings directly, we compute this transformed prefix value at every position and count how many times each value has appeared before.

This turns the problem into a standard prefix-frequency counting problem solvable in linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every substring explicitly
Optimal	O(n)	O(n)	Uses transformed prefix sums with a hash map

Algorithm Walkthrough

1. Initialize counters for zeros and ones.

We maintain running counts while scanning the string from left to right. 2. Define the transformed prefix value.

At every position, compute:

$$key = zeros \times num2 - ones \times num1$$

This value uniquely represents the balance needed for valid substrings. 3. Use a hash map to store frequencies.

The hash map stores how many times each key has appeared so far.

Initially:

• key = 0 has frequency 1

This represents the empty prefix before processing any characters. 4. Process the string character by character.

For each character:

• increment zeros if the character is '0'
• increment ones if the character is '1'

Then recompute the current key. 5. Count valid substrings ending at the current position.

If the same key appeared earlier k times, then there are k valid substrings ending at the current position.

Why?

Because every earlier occurrence of the same transformed prefix value forms a substring satisfying the ratio condition. 6. Update the hash map.

After using the current key, increment its frequency in the map. 7. Continue until the entire string is processed. 8. Return the accumulated answer.

Why it works

The algorithm relies on the invariant that two prefixes with the same transformed value:

$$zeros \times num2 - ones \times num1$$

define a substring whose zero-to-one ratio equals num1 : num2.

Every valid substring corresponds to exactly one pair of equal transformed prefix values, and every such pair defines a valid substring. Therefore, counting equal prefix states correctly counts all valid substrings.

Python Solution

from collections import defaultdict

class Solution:
    def fixedRatio(self, s: str, num1: int, num2: int) -> int:
        prefix_frequency = defaultdict(int)
        prefix_frequency[0] = 1

        zeros = 0
        ones = 0
        answer = 0

        for ch in s:
            if ch == '0':
                zeros += 1
            else:
                ones += 1

            key = zeros * num2 - ones * num1

            answer += prefix_frequency[key]

            prefix_frequency[key] += 1

        return answer

The implementation follows the exact logic described in the algorithm walkthrough.

We first create a hash map called prefix_frequency. This stores how many times each transformed prefix value has occurred.

The entry prefix_frequency[0] = 1 is important because it represents the empty prefix before processing any characters. Without this initialization, substrings starting at index 0 would not be counted correctly.

As we iterate through the string:

• we update either zeros or ones
• compute the transformed prefix value
• add the number of previous occurrences of that value to the answer
• store the current prefix state in the map

The use of defaultdict(int) simplifies frequency handling because missing keys automatically default to zero.

Since each character is processed once and each hash map operation is constant time on average, the solution runs in linear time.

Go Solution

func fixedRatio(s string, num1 int, num2 int) int64 {
	prefixFrequency := make(map[int]int64)
	prefixFrequency[0] = 1

	zeros := 0
	ones := 0
	var answer int64 = 0

	for _, ch := range s {
		if ch == '0' {
			zeros++
		} else {
			ones++
		}

		key := zeros*num2 - ones*num1

		answer += prefixFrequency[key]

		prefixFrequency[key]++
	}

	return answer
}

The Go implementation mirrors the Python solution closely.

A map[int]int64 is used because the number of valid substrings may exceed the range of a 32-bit integer.

The transformed prefix value is stored as an int, while frequencies and the final answer use int64.

Unlike Python's defaultdict, Go maps return the zero value automatically for missing keys, so explicit initialization beyond prefixFrequency[0] = 1 is unnecessary.

Worked Examples

Example 1

Input:

s = "0110011"
num1 = 1
num2 = 2

We compute:

$$key = zeros \times 2 - ones \times 1$$

Step	Char	Zeros	Ones	Key	Previous Frequency	Added to Answer	Total Answer
Start	-	0	0	0	1	-	0
0	0	1	0	2	0	0	0
1	1	1	1	1	0	0	0
2	1	1	2	0	1	1	1
3	0	2	2	2	1	1	2
4	0	3	2	4	0	0	2
5	1	3	3	3	0	0	2
6	1	3	4	2	2	2	4

Final answer:

4

Example 2

Input:

s = "10101"
num1 = 3
num2 = 1

We compute:

$$key = zeros \times 1 - ones \times 3$$

Step	Char	Zeros	Ones	Key	Previous Frequency	Added
Start	-	0	0	0	1	-
0	1	0	1	-3	0	0
1	0	1	1	-2	0	0
2	1	1	2	-5	0	0
3	0	2	2	-4	0	0
4	1	2	3	-7	0	0

No transformed prefix value repeats, so no valid substrings exist.

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed once
Space	O(n)	The hash map may store up to O(n) unique prefix states

The algorithm performs a single pass through the string. Each iteration does constant-time work consisting of arithmetic operations and hash map lookups.

In the worst case, every transformed prefix value is unique, so the hash map grows to size O(n).

Test Cases

sol = Solution()

# Provided example 1
assert sol.fixedRatio("0110011", 1, 2) == 4

# Provided example 2
assert sol.fixedRatio("10101", 3, 1) == 0

# Single valid substring
assert sol.fixedRatio("01", 1, 1) == 1

# Entire string valid
assert sol.fixedRatio("0011", 1, 1) == 1

# Multiple overlapping valid substrings
assert sol.fixedRatio("0101", 1, 1) == 4

# All zeros, impossible ratio
assert sol.fixedRatio("0000", 1, 1) == 0

# All ones, impossible ratio
assert sol.fixedRatio("1111", 1, 1) == 0

# Ratio 2:1
assert sol.fixedRatio("001001", 2, 1) == 4

# No valid substrings
assert sol.fixedRatio("11011", 2, 3) == 0

# Long repeated pattern
assert sol.fixedRatio("0101010101", 1, 1) == 25

# Minimum length string
assert sol.fixedRatio("0", 1, 1) == 0

# Another balanced case
assert sol.fixedRatio("1100", 1, 1) == 2

Test	Why
"0110011", 1, 2	Validates the main example
"10101", 3, 1	Confirms zero-answer handling
"01", 1, 1	Smallest non-trivial valid case
"0011", 1, 1	Entire string forms one valid substring
"0101", 1, 1	Tests overlapping valid substrings
"0000", 1, 1	No ones present
"1111", 1, 1	No zeros present
"001001", 2, 1	Non-equal ratio validation
"11011", 2, 3	No matching ratio exists
"0101010101", 1, 1	Stress test with many matches
"0", 1, 1	Minimum input size
"1100", 1, 1	Multiple balanced substrings

Edge Cases

One important edge case occurs when the string contains only one type of character. For example, "00000" contains no 1s. Any ratio requiring at least one 1 is impossible to satisfy. A naive implementation might accidentally divide by zero or incorrectly treat such substrings as valid. This implementation avoids division entirely and instead uses the transformed linear equation, so these cases are handled naturally.

Another important case is substrings starting at index 0. Many prefix-sum solutions fail here if they do not initialize the frequency map correctly. The line:

prefix_frequency[0] = 1

ensures that whenever the current prefix itself satisfies the required ratio, it is counted correctly.

A third edge case involves many overlapping valid substrings. For example, "010101" with ratio 1:1 contains numerous balanced substrings sharing endpoints and overlaps. The frequency-based counting method correctly counts all pairs of matching transformed prefix states, ensuring no valid substring is missed or double-counted.

A final subtle case is large outputs. Since there can be O(n^2) valid substrings in highly repetitive strings, the answer may become very large. The Go solution therefore uses int64 for the answer and frequencies to avoid overflow.