The only string that does not match \(S_i\) in any position is the string obtained by flipping all 0s and 1s of \(S_i\) (denote it \(S'_i\)).

Thus, the condition for the answer is equivalent to being a string of length \(M\) that is none of \(S'_1, \dots, S'_N\).

Let \(m = \lceil \log_{2} (N+1) \rceil\).

Case \(M < m\)

Among all \(2^M\) possible strings \(T\), we need to find one that differs from all of \(S'_1, \dots, S'_N\). This can be done by preparing a zero-filled array of length \(2^M\), setting the elements at indices \(S'_1, \dots, S'_N\) to \(1\), and then finding an index with value \(0\).

Case \(M \geq m\)

• The prefixes of the first \(m\) characters of each of \(S'_1, \dots, S'_N\) have at most \(N\) distinct values.
• The number of possible values for the prefix of the first \(m\) characters of \(T\) is \(2^m = 2^{\lceil \log_{2} (N+1) \rceil}\).

Since \(2^m = 2^{\lceil \log_{2} (N+1) \rceil} \geq N+1 > N\), there exists a string of length \(m\) that is none of the first \(m\) characters of \(S'_1, \dots, S'_N\). Any \(T\) whose prefix is this string will be an answer.

The method for finding the prefix of length \(m\) is the same as in the case \(M < m\).

Time Complexity

Since \(2^{\min(M, m)} = O(N)\), the time complexity is \(O(NM)\) in each case.

Proposed by: sheyasutaka