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
。
解法
方法一:数学
假设字符串 长度为 ,那么长度为 的子串共有 个,每个子串都可以翻转,因此共有 种翻转方式。
时间复杂度 ,空间复杂度 。其中 为字符串 的长度。
1 2 3 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 |
|