[LeetCode] Number of Substrings With Fixed Ratio

2489. Number of Substrings With Fixed Ratio

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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
long long fixedRatio(string s, int num1, int num2) {
unordered_map<long long, int> freq{{0, 1}};
long long res = 0, now = 0;
for (auto& ch : s) {
if (ch == '0') now += num2;
else now -= num1;
res += freq[now];
freq[now] += 1;
}
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/12/21/PS/LeetCode/number-of-substrings-with-fixed-ratio/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.