2489. Number of Substrings With Fixed Ratio π
Description
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
andnum2 = 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
andy
are coprime ifgcd(x, y) == 1
wheregcd(x, y)
is the greatest common divisor ofx
andy
.
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
andnum2
are coprime integers.
Solutions
Solution 1: Prefix Sum + Counting
We use $one[i]$ to represent the number of $1$s in the substring $s[0,..i]$, and $zero[i]$ to represent the number of $0$s 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$.
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|