class Solution {
public:
int countDistinctStrings(string s, int k) {
}
};
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 <= 105s[i] 是 0 或 1。原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 3.9 MB, 提交时间: 2023-10-17 14:21:27
func countDistinctStrings(s string, k int) int {
res := 2
mod := 1000000007
for x := 1; x <= len(s) - k; x++ {
res = res * 2 % mod
}
return res
}
cpp 解法, 执行用时: 12 ms, 内存消耗: 9.2 MB, 提交时间: 2023-10-17 14:20:18
class Solution {
public:
int countDistinctStrings(string s, int k) {
int res = 2;
int mod = 1000000007;
for (int x = 1; x <= s.length() - k; ++x) {
res = res * 2 % mod;
}
return res;
}
};
rust 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2023-10-17 14:16:40
impl Solution {
pub fn count_distinct_strings(s: String, k: i32) -> i32 {
let n = s.len();
let mut ans = 2;
for i in 1..=n - k as usize {
ans = ans * 2 % 1000000007;
}
ans
}
}
javascript 解法, 执行用时: 52 ms, 内存消耗: 42.8 MB, 提交时间: 2023-10-17 14:16:14
/**
* @param {string} s
* @param {number} k
* @return {number}
*/
var countDistinctStrings = function(s, k) {
let x = 1;
for(let i = 1; i <= s.length - k + 1; i ++){
x *= 2;
x %= 1e9 + 7;
}
return x;
};
java 解法, 执行用时: 3 ms, 内存消耗: 42.4 MB, 提交时间: 2023-10-17 14:14:27
class Solution {
public int countDistinctStrings(String s, int k) {
long res = 2;
final int mod = (int) 1e9 + 7;
for (int x = 1; x <= s.length() - k; x++) {
res = res * 2 % mod;
}
return (int) res;
}
}
python3 解法, 执行用时: 40 ms, 内存消耗: 16.6 MB, 提交时间: 2023-10-17 14:14:06
class Solution:
def countDistinctStrings(self, s: str, k: int) -> int:
# 脑筋急转弯
# 由于每一段区间只有翻转和不翻转
# 可以翻转的长度为 (n - k) + 1
# 所以可能性为 2**p
return pow(2, (len(s)-k+1), int(1e9+7))