2489. 固定比率的子字符串数 🔒 

English Version

题目描述

给定一个二进制字符串 s 和两个整数 num1 和 num2。num1 和 num2 为互质。

比率子串 是 s 的子串，其中子串中 0 的数量与 1 的数量之比正好是 num1 : num2。

例如，如果 num1 = 2 和 num2 = 3，那么 "01011" 和 "1110000111" 是比率子串，而 "11000" 不是。

返回 s 的非空比率子串的个数。

注意:

子串是字符串中连续的字符序列。
如果 gcd(x, y) == 1，则 x 和 y 为互质，其中 gcd(x, y) 为 x 和 y 的最大公约数。

示例 1:

输入: s = "0110011", num1 = 1, num2 = 2
输出: 4
解释: 有 4 个非空的比率子串。
- 子字符串 s[0..2]: "0110011"。它包含一个 0 和两个 1。比例是 1:2。
- 子字符串 s[1..4]: "0110011"。它包含一个 0 和两个 1。比例是 1:2。
- 子字符串 s[4..6]: "0110011"。它包含一个 0 和两个 1。比例是 1:2。
- 子字符串 s[1..6]: "0110011"。它包含两个 0 和四个 1。比例是 2:4 == 1:2。
它可以显示没有更多的比率子串。

示例 2:

输入: s = "10101", num1 = 3, num2 = 1
输出: 0
解释: s 没有比率子串，返回 0。

提示:

1 <= s.length <= 10⁵
1 <= num1, num2 <= s.length
num1 和 num2 互质。

解法

方法一：前缀和 + 计数

我们用 $one[i]$ 表示字符串 $s[0,..i]$ 中 $1$ 的个数，用 $zero[i]$ 表示字符串 $s[0,..i]$ 中 $0$ 的个数。子串符合条件，需要满足

$$ \frac{zero[j] - zero[i]}{one[j] - one[i]} = \frac{num1}{num2} $$

其中 $i < j$。我们可以将上式转化为

$$ one[j] \times num1 - zero[j] \times num2 = one[i] \times num1 - zero[i] \times num2 $$

遍历到下标 $j$ 时，我们只需要统计有多少个下标 $i$ 满足上式即可。因此，我们可以用哈希表记录 $one[i] \times num1 - zero[i] \times num2$ 出现的次数，遍历到下标 $j$ 时，只需要统计 $one[j] \times num1 - zero[j] \times num2$ 出现的次数即可。

哈希表初始时只有一个键值对 $(0, 1)$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串 $s$ 的长度。

Python3

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

Java

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;
    }
}

C++

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;
    }
};

Go

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)
}