2629. Number of Substrings With Fixed Ratio

Medium
Hash Table
Math
String
Prefix Sum

Description

Hints

Hint 1
Let Func(i) denote the number of 0’s in the prefix [0…i]. We want to find the number of pairs of indices L and R such that Func(R) - Func(L) : R - L - Func(R) + Func(L) = num1 : num2.
Hint 2
It is better to simplify the formula.
Hint 3
Func(R) * (num1 + num2) - R * num1 = Func(L) * (num1 + num2) - L * num1.
Hint 4
Iterate from left to right and use a hash map to count the number of indices having the same value for the above formula.

Statistics

Acceptance
57.2%
Submissions
2,832
Accepted
1,620