Question

2533. 好二进制字符串的数量

English Version

题目描述

给你四个整数 minLength、maxLength、oneGroup 和 zeroGroup 。

好 二进制字符串满足下述条件：

• 字符串的长度在 [minLength, maxLength] 之间。
• 每块连续 1 的个数是 oneGroup 的整数倍
  • 例如在二进制字符串 00_11_0_1111_00 中，每块连续 1 的个数分别是[2,4] 。
• 每块连续 0 的个数是 zeroGroup 的整数倍
  • 例如在二进制字符串 _00_11_0_1111_00_ 中，每块连续 0 的个数分别是 [2,1,2] 。

请返回 好 二进制字符串的个数。答案可能很大，请返回对 109 + 7 取余 后的结果。

注意：0 可以被认为是所有数字的倍数。

 

示例 1：

输入：minLength = 2, maxLength = 3, oneGroup = 1, zeroGroup = 2
输出：5
解释：在本示例中有 5 个好二进制字符串: "00", "11", "001", "100", 和 "111" 。
可以证明只有 5 个好二进制字符串满足所有的条件。

示例 2：

输入：minLength = 4, maxLength = 4, oneGroup = 4, zeroGroup = 3
输出：1
解释：在本示例中有 1 个好二进制字符串: "1111" 。
可以证明只有 1 个好字符串满足所有的条件。

 

提示：

• 1 <= minLength <= maxLength <= 105
• 1 <= oneGroup, zeroGroup <= maxLength

解法

方法一：动态规划

我们定义 $f[i]$ 表示长度为 $i$ 的字符串中满足条件的个数。状态转移方程为：

$$ f[i] = \begin{cases} 1 & i = 0 \ f[i - oneGroup] + f[i - zeroGroup] & i \geq 1 \end{cases} $$

最终答案为 $f[minLength] + f[minLength + 1] + \cdots + f[maxLength]$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n=maxLength$。

class Solution:
  def goodBinaryStrings(
    self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int
  ) -> int:
    mod = 10**9 + 7
    f = [1] + [0] * maxLength
    for i in range(1, len(f)):
      if i - oneGroup >= 0:
        f[i] += f[i - oneGroup]
      if i - zeroGroup >= 0:
        f[i] += f[i - zeroGroup]
      f[i] %= mod
    return sum(f[minLength:]) % mod

class Solution {
  public int goodBinaryStrings(int minLength, int maxLength, int oneGroup, int zeroGroup) {
    final int mod = (int) 1e9 + 7;
    int[] f = new int[maxLength + 1];
    f[0] = 1;
    for (int i = 1; i <= maxLength; ++i) {
      if (i - oneGroup >= 0) {
        f[i] = (f[i] + f[i - oneGroup]) % mod;
      }
      if (i - zeroGroup >= 0) {
        f[i] = (f[i] + f[i - zeroGroup]) % mod;
      }
    }
    int ans = 0;
    for (int i = minLength; i <= maxLength; ++i) {
      ans = (ans + f[i]) % mod;
    }
    return ans;
  }
}

class Solution {
public:
  int goodBinaryStrings(int minLength, int maxLength, int oneGroup, int zeroGroup) {
    const int mod = 1e9 + 7;
    int f[maxLength + 1];
    memset(f, 0, sizeof f);
    f[0] = 1;
    for (int i = 1; i <= maxLength; ++i) {
      if (i - oneGroup >= 0) {
        f[i] = (f[i] + f[i - oneGroup]) % mod;
      }
      if (i - zeroGroup >= 0) {
        f[i] = (f[i] + f[i - zeroGroup]) % mod;
      }
    }
    int ans = 0;
    for (int i = minLength; i <= maxLength; ++i) {
      ans = (ans + f[i]) % mod;
    }
    return ans;
  }
};

func goodBinaryStrings(minLength int, maxLength int, oneGroup int, zeroGroup int) (ans int) {
  const mod int = 1e9 + 7
  f := make([]int, maxLength+1)
  f[0] = 1
  for i := 1; i <= maxLength; i++ {
    if i-oneGroup >= 0 {
      f[i] += f[i-oneGroup]
    }
    if i-zeroGroup >= 0 {
      f[i] += f[i-zeroGroup]
    }
    f[i] %= mod
  }
  for _, v := range f[minLength:] {
    ans = (ans + v) % mod
  }
  return
}

function goodBinaryStrings(
  minLength: number,
  maxLength: number,
  oneGroup: number,
  zeroGroup: number,
): number {
  const mod = 10 ** 9 + 7;
  const f: number[] = Array(maxLength + 1).fill(0);
  f[0] = 1;
  for (let i = 1; i <= maxLength; ++i) {
    if (i >= oneGroup) {
      f[i] += f[i - oneGroup];
    }
    if (i >= zeroGroup) {
      f[i] += f[i - zeroGroup];
    }
    f[i] %= mod;
  }
  return f.slice(minLength).reduce((a, b) => a + b, 0) % mod;
}