Question

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 <= 105
• 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$ 的长度。

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

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

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

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