Problem

You are given a binary string s and a positive integer k.

You can apply the following operation on the string any number of times:

  • Choose any substring of size k from s and flip all its characters, that is, turn all 1’s into 0’s, and all 0’s into 1’s.

Return the number ofdistinct strings you can obtain. Since the answer may be too large, return it modulo 109 + 7.

Note that:

  • A binary string is a string that consists only of the characters 0 and 1.
  • A substring is a contiguous part of a string.

Examples

Example 1:

1
2
3
4
5
6
7
8

Input: s = "1001", k = 3
Output: 4
Explanation: We can obtain the following strings:
- Applying no operation on the string gives s = "1001".
- Applying one operation on the substring starting at index 0 gives s = "_**011**_ 1".
- Applying one operation on the substring starting at index 1 gives s = "1 _**110**_ ".
- Applying one operation on both the substrings starting at indices 0 and 1 gives s = "_**0000**_ ".
It can be shown that we cannot obtain any other string, so the answer is 4.

Example 2:

1
2
3
4
5
6

Input: s = "10110", k = 5
Output: 2
Explanation: We can obtain the following strings:
- Applying no operation on the string gives s = "10110".
- Applying one operation on the whole string gives s = "01001".
It can be shown that we cannot obtain any other string, so the answer is 2.

Constraints:

  • 1 <= k <= s.length <= 10^5
  • s[i] is either 0 or 1.

Solution

Method 1 – Linear Algebra (Parity of Flips)

Intuition

Flipping any substring of length k is a linear operation (XOR with a mask). The set of all possible strings is the span of the initial string and all possible flip masks. The number of distinct strings is 2^d, where d is the number of independent flip masks (which is n-k+1 for k < n, or 2 for k = n).

Approach

  1. If k == n, only two strings are possible: original and fully flipped.
  2. If k < n, each substring of length k can be flipped independently, but overlapping flips interact. The number of distinct strings is 2^(n-k+1).
  3. Return the answer modulo 1e9+7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#include <string>
#include <cmath>
using namespace std;
const int MOD = 1e9+7;
class Solution {
public:
    int numberOfDistinctBinaryStrings(string s, int k) {
        int n = s.size();
        if (k == n) return 2;
        long long res = 1;
        for (int i = 0; i < n-k+1; ++i) res = (res*2)%MOD;
        return res;
    }
};
1
2
3
4
5
6
7
8

func numberOfDistinctBinaryStrings(s string, k int) int {
    n := len(s)
    mod := int(1e9+7)
    if k == n { return 2 }
    res := 1
    for i := 0; i < n-k+1; i++ { res = (res*2)%mod }
    return res
}
1
2
3
4
5
6
7
8
9

class Solution {
    public int numberOfDistinctBinaryStrings(String s, int k) {
        int n = s.length(), MOD = (int)1e9+7;
        if (k == n) return 2;
        long res = 1;
        for (int i = 0; i < n-k+1; ++i) res = (res*2)%MOD;
        return (int)res;
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    fun numberOfDistinctBinaryStrings(s: String, k: Int): Int {
        val n = s.length; val MOD = 1_000_000_007
        if (k == n) return 2
        var res = 1L
        repeat(n-k+1) { res = (res*2)%MOD }
        return res.toInt()
    }
}
1
2
3
4
5

class Solution:
    def numberOfDistinctBinaryStrings(self, s: str, k: int) -> int:
        n, MOD = len(s), 10**9+7
        if k == n: return 2
        return pow(2, n-k+1, MOD)
1
2
3
4
5
6
7
8
9

impl Solution {
    pub fn number_of_distinct_binary_strings(s: String, k: i32) -> i32 {
        let n = s.len() as i32;
        if k == n { return 2; }
        let mut res = 1i64;
        for _ in 0..(n-k+1) { res = (res*2)%1_000_000_007; }
        res as i32
    }
}
1
2
3
4
5
6
7

function numberOfDistinctBinaryStrings(s: string, k: number): number {
    const n = s.length, MOD = 1e9+7;
    if (k === n) return 2;
    let res = 1;
    for (let i = 0; i < n-k+1; ++i) res = (res*2)%MOD;
    return res;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)