Question

2450. 应用操作后不同二进制字符串的数量

English Version

题目描述

给定一个 二进制 字符串 s 和一个正整数 k。

你可以对字符串应用以下操作 任意 次数:

• 从 s 中选择任何大小为 k 的子字符串，将其所有字符 翻转，即将所有 1 都变成 0，所有 0 都变成 1。

返回_您可以获得的 不同 字符串的数量。_因为答案可能太大，所以对 109 + 7 取模 后返回。

注意:

• 二进制字符串是 仅由 字符 0 和 1 组成的字符串。

• 子字符串是字符串的连续部分。

 

示例 1:

输入: s = "1001", k = 3
输出: 4
解释: 我们可以获得以下字符串:
- 对字符串不应用任何操作将得到 s = "1001"。
- 对从下标 0 开始的子字符串应用一个操作，得到 s = "0111"。
- 对从下标 1 开始的子字符串应用一个操作，得到 s = "1110"。
- 对从下标 0 和 1 开始的两个子字符串都应用一个操作，得到 s = "0000"。
可以证明，我们不能获得任何其他字符串，所以答案是 4。

示例 2:

输入: s = "10110", k = 5
输出: 2
解释: 我们可以获得以下字符串:
- 对字符串不执行任何操作，将得到 s = "10110"。
- 对整个字符串应用一个操作将得到 s = "01001"。
可以证明，我们不能获得任何其他字符串，所以答案是 2。

 

提示:

• 1 <= k <= s.length <= 105
• s[i] 是 0 或 1。

解法

方法一：数学

假设字符串 $s$ 长度为 $n$，那么长度为 $k$ 的子串共有 $n - k + 1$ 个，每个子串都可以翻转，因此共有 $2^{n - k + 1}$ 种翻转方式。

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

class Solution:
  def countDistinctStrings(self, s: str, k: int) -> int:
    return pow(2, len(s) - k + 1) % (10**9 + 7)

class Solution {
  public static final int MOD = (int) 1e9 + 7;

  public int countDistinctStrings(String s, int k) {
    int ans = 1;
    for (int i = 0; i < s.length() - k + 1; ++i) {
      ans = (ans * 2) % MOD;
    }
    return ans;
  }
}

class Solution {
public:
  const int mod = 1e9 + 7;

  int countDistinctStrings(string s, int k) {
    int ans = 1;
    for (int i = 0; i < s.size() - k + 1; ++i) {
      ans = (ans * 2) % mod;
    }
    return ans;
  }
};

func countDistinctStrings(s string, k int) int {
  const mod int = 1e9 + 7
  ans := 1
  for i := 0; i < len(s)-k+1; i++ {
    ans = (ans * 2) % mod
  }
  return ans
}