Coding

Number of Distinct Binary Strings After Applying Operations

Asked at

M2P Fintech

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The 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 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.

**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.

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.

Consider s = "110010" and k = 4. What is the number of distinct binary strings that can be formed?

1 <= k <= s.length <= 105
s[i] is either 0 or 1.

cpp

class Solution {
public:
    int countDistinctStrings(string s, int k) {
        // Your code goes here
    }
};

java

class Solution {
    public int countDistinctStrings(String s, int k) {
        // Your code goes here
    }
}

python

class Solution:
    def countDistinctStrings(self, s: str, k: int) -> int:
        # Your code goes here

javascript

class Solution {
    countDistinctStrings(s, k) {
        // Your code goes here
    }
}

csharp

public class Solution {
    public int CountDistinctStrings(string s, int k) {
        // Your code goes here
    }
}

func countDistinctStrings(s string, k int) int {
}

Stuck? Show a way to structure it+

01Represent each length-k flip as a binary vector.
02Observe operations compose by XOR and can be used at most once modulo two.
03Find the rank of the generated vectors.
04Return two to that rank modulo MOD.
05Handle k equal to n separately.

Reference answer

Flipping a fixed-length substring is XOR with its indicator vector. Because applying the same flip twice cancels, reachable strings are the original string plus every vector in the span of the n-k+1 operation vectors over GF(2); the starting bits do not affect the count. For k == n, there is one generator and therefore two reachable strings. More generally, the consecutive length-k vectors are linearly independent for the usual range 1 <= k <= n, so the rank is n-k+1 and the answer is 2^(n-k+1) mod 1e9+7. Explain this independence by looking at the leftmost coordinate of a nonzero combination. Compute modular exponentiation in O(log n) time and O(1) space. Do not enumerate strings, which would be exponential.

Then expect these follow-ups

How would arbitrary flip masks change the solution?
Tests: Gaussian elimination
Why is the original string irrelevant to the count?
Tests: XOR structure

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question