Number of Substrings With Fixed Ratio

Number of Substrings With Fixed Ratio

What is this problem about?

The Number of Substrings With Fixed Ratio problem gives you a binary string and two integers num1 and num2. Count substrings where the count of '0's to count of '1's equals num1:num2. This coding problem uses prefix sum with a hash map, similar to the "subarray sum divisible by k" pattern but adapted for a ratio condition.

Why is this asked in interviews?

Intuit asks this to test the transformation of a ratio condition into a linear prefix sum equation. The key: for a substring with cnt0 zeros and cnt1 ones, cnt0 * num2 == cnt1 * num1 ⟺ cnt0 * num2 - cnt1 * num1 == 0. Define diff[i] = cnt0[i] * num2 - cnt1[i] * num1 using prefix counts. Count pairs where diff[i] == diff[j]. The math, hash table, string, and prefix sum interview pattern is directly demonstrated.

Algorithmic pattern used

Prefix difference hash map. Compute running diff = (count_of_0s * num2) - (count_of_1s * num1). Maintain a frequency map of all previous diff values. For each position i, the number of valid substrings ending here = frequency of the current diff value in the map. Increment the map for the current diff. Initialize map with {0: 1} for the empty prefix.

Example explanation

s="0110", num1=1, num2=2. Need cnt0/cnt1 = 1/2, i.e., diff = cnt02 - cnt11 = 0. Prefix: start with map={0:1}, diff=0.

• s[0]='0': diff=01-0... wait: diff = cnt0num2 - cnt1num1 = 12-0*1=2. map={0:1}. Add freq[2]=0. map={0:1,2:1}.
• s[1]='1': cnt0=1,cnt1=1. diff=12-11=1. freq[1]=0. map={0:1,2:1,1:1}.
• s[2]='1': cnt0=1,cnt1=2. diff=12-21=0. freq[0]=1. Count+=1. map={0:2,2:1,1:1}.
• s[3]='0': cnt0=2,cnt1=2. diff=22-21=2. freq[2]=1. Count+=1. Total=2.

Common mistakes candidates make

• Not initializing the hash map with {0:1} (misses substrings starting from index 0).
• Using floating-point ratio comparison instead of integer cross-multiplication.
• Off-by-one in counting: add freq[diff] first, then update the map.
• Not handling the edge case where num1=0 or num2=0.

Interview preparation tip

Ratio-based substring counting always converts to "count pairs with equal prefix difference." The key transformation: cnt_a/cnt_b == p/q ⟺ cnt_a*q - cnt_b*p == 0. This reduces ratio matching to a standard prefix hash map problem. Practice similar problems: "equal '0's and '1's ratio," "subarrays with k times more '1's than '0's." The transformation technique is universally applicable to any ratio condition on counts.