跳转至

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

题目描述

给定一个 二进制 字符串 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$ 的长度。

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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;
    }
};

1
2
3
4
5
6
7
8
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
}

评论