2450. Number of Distinct Binary Strings After Applying Operations

Description

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 of distinct 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.

 

Example 1:

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 = "0111".
- Applying one operation on the substring starting at index 1 gives s = "1110".
- 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:

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 <= 105
  • s[i] is either 0 or 1.

Solutions

Solution 1: Mathematics

Assume the length of the string $s$ is $n$. Then there are $n - k + 1$ substrings of length $k$, and each substring can be flipped, so there are $2^{n - k + 1}$ ways to flip.

The time complexity is $O(n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the string $s$.

Python Code
1
2
3

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

Java Code
 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;
    }
}

C++ Code
 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;
    }
};

Go Code
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
}