LeetCode 2489. Number of Substrings With Fixed Ratio Solution in Java, C++, Python & Go | Explanation + Code

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 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.

 

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 and num2 are coprime integers.

Solutions

Solution 1: Prefix Sum + Counting

We use one[i] to represent the number of 1s in the substring s[0,..i], and zero[i] to represent the number of 0s in the substring s[0,..i]. A substring meets the condition if

^{zero[j] - zero[i]}⁄_{one[j] - one[i]} = ^num1⁄_num2

where i < j. We can transform the above equation into

one[j] × num1 - zero[j] × num2 = one[i] × num1 - zero[i] × 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] × num1 - zero[i] × num2, and when we iterate to index j, we only need to count the number of occurrences of one[j] × num1 - zero[j] × 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.

PythonJavaC++Go

class Solution: def fixedRatio(self, s: str, num1: int, num2: int) -> int: n0 = n1 = 0 ans = 0 cnt = Counter({0: 1}) for c in s: n0 += c == '0' n1 += c == '1' x = n1 * num1 - n0 * num2 ans += cnt[x] cnt[x] += 1 return ans(code-box)

class Solution { public long fixedRatio(String s, int num1, int num2) { long n0 = 0, n1 = 0; long ans = 0; Map<Long, Long> cnt = new HashMap<>(); cnt.put(0L, 1L); for (char c : s.toCharArray()) { n0 += c == '0' ? 1 : 0; n1 += c == '1' ? 1 : 0; long x = n1 * num1 - n0 * num2; ans += cnt.getOrDefault(x, 0L); cnt.put(x, cnt.getOrDefault(x, 0L) + 1); } return ans; } }(code-box)

using ll = long long; class Solution { public: long long fixedRatio(string s, int num1, int num2) { ll n0 = 0, n1 = 0; ll ans = 0; unordered_map<ll, ll> cnt; cnt[0] = 1; for (char& c : s) { n0 += c == '0'; n1 += c == '1'; ll x = n1 * num1 - n0 * num2; ans += cnt[x]; ++cnt[x]; } return ans; } };(code-box)

func fixedRatio(s string, num1 int, num2 int) int64 { n0, n1 := 0, 0 ans := 0 cnt := map[int]int{0: 1} for _, c := range s { if c == '0' { n0++ } else { n1++ } x := n1*num1 - n0*num2 ans += cnt[x] cnt[x]++ } return int64(ans) }(code-box)