The overall approach is to do casework on all possible ~T~. In each case, we first characterize all the strings that do not contain ~T~ (call these good states). Based on this characterization, we then look for a measure of how far ~S~ is from a good state and a greedy algorithm that repeatedly brings ~S~ closer to a good state.

Formally, in each of the cases, we will find a function ~f(S)~ such that ~f(S) = 0~ at all good states, ~f(S') \ge f(S)-1~ for all ~S,S'~ where ~S'~ is obtained from ~S~ by one reversal, and a greedy algorithm that finds an ~S'~ from any non-good state ~S~ such that ~f(S') = f(S)-1~. It will then follow that ~f(S)~ is the answer for any string ~S~.

We can reduce the number of cases by half by noting that the answer remains the same if all the bits in ~S~ and ~T~ are flipped, so we may WLOG let ~T_1 = \tt 0~.

Subtask 1

We need to consider the case ~T = \tt 0~.

A good state is when the string is composed of only ~\tt 1~s. Therefore the answer is ~0~ if ~S~ contains only ~\tt 1~s, and otherwise, the answer is ~-1~.

Subtask 2

We need to consider the case ~T = \tt 01~.

A good state is when the string is a block of consecutive ~\tt 1~s followed by a block of consecutive ~\tt 0~s. This encourages us to look at blocks of consecutive ~\tt 1~s, and we might conjecture that the answer is the number of blocks of consecutive ~\tt 1~s that are not at the beginning of ~S~. Indeed, this number can decrease by at most ~1~ per reversal, and a greedy algorithm that looks for the first block of ~\tt 1~s that is not at the beginning and performs a reversal to combine it with the beginning (e.g. ~\tt 11[00111]01 \to \tt 11[11100]01~ or ~\tt [001]011 \to \tt [100]011~) works.

Alternatively, the answer is just the number of times ~T = \tt 01~ appears in ~S~ as a substring, which can be proven similarly.

Subtask 3

We need to consider the case ~T = \tt 00~.

A good state is when the string does not contain any blocks of two or more consecutive ~\tt 0~s. If ~S~ has more ~\tt 0~s than the number of ~\tt 1~s plus ~1~, then the answer is ~-1~ since no rearrangement of the characters of ~S~ is a good state.

Otherwise, the answer is the sum of ~(\text{block size}-1)~ over all blocks of consecutive ~\tt 0~s. Whenever ~S~ is not a good state, there exists a substring ~\tt 11~ in ~S~, and we can greedily perform a reversal to "cut off" a ~\tt 0~ from a block and "insert" it into this ~\tt 11~ (e.g. ~\tt 00[01010111101]1 \to \tt 00[10111101010]1~).

Alternatively, the answer is just the number of times ~T = \tt 00~ appears in ~S~ as a substring if ~((\text{# 0s in }S) \le (\text{# 1s in }S)+1)~, otherwise ~-1~.

Subtask 4

We need to consider the cases ~T = \tt 001~ and ~T = \tt 011~. By reversing and flipping the bits of ~S~ and ~T~, these cases are equivalent, so we will only describe ~T = \tt 011~.

A good state is when the string has a prefix of consecutive ~\tt 1~s and no blocks of two or more consecutive ~\tt 1~s after that. The answer is the number of blocks of two or more consecutive ~\tt 1~s that are not in the prefix of ~\tt 1~s, and a greedy algorithm similar to ~T = \tt 01~ can prove this.

Alternatively, the answer is just the number of times ~T = \tt 011~ appears in ~S~ as a substring.

Subtask 5

We need to consider the cases ~T = \tt 010~ and ~T = \tt 011~. The case ~T = \tt 011~ was solved in subtask 4, so we need to solve ~T = \tt 010~.

A good state is when the string does not contain any blocks of exactly one consecutive ~\tt 1~. In one reversal, it is possible to "merge" up to ~2~ blocks of exactly one ~\tt 1~ (e.g. ~\tt 01[011001]0 \to \tt 01[100110]0~). Therefore, if ~S~ contains ~x~ blocks of exactly one consecutive ~\tt 1~, the answer is ~\lceil \frac{x}{2} \rceil~.

Alternatively, the answer is just the number of times ~T = \tt 010~ appears in ~S~ as a substring divided by ~2~, rounded up.

Subtask 6

The remaining case is when ~T = \tt 000~.

Similar to when ~T = \tt 00~, a good state is when the string does not contain any blocks of three or more consecutive ~\tt 0~s. If ~S~ has more ~\tt 0~s than twice the number of ~\tt 1~s plus ~2~, then the answer is ~-1~ since no rearrangement of the characters of ~S~ is a good state.

In this case, it might help to analyze how reversals behave on the blocks of ~\tt 0~s in ~S~ more closely. Suppose the ~\tt 1~s in ~S~ separate ~S~ into blocks of ~x_1,\dots,x_k~ consecutive ~\tt 0~s, where some ~x_i~ may be zero. Then a reversal takes any two ~x_i,x_j~ (where ~i < j~), changes them to two new block sizes ~y,x_i+x_j-y~ (where any ~0 \le y \le x_i+x_j~ is possible), and reverses the order of the blocks in between ~i~ and ~j~. We can view ~x_1,\dots,x_k~ as a multiset since the order is not important.

We can use blocks of size ~1~ to cut off pieces of size ~1~ from larger blocks, and we can also use blocks of size ~0~ to cut off pieces of size ~2~ from larger blocks. Intuitively, we should use the size ~0~ blocks to cut off pieces of size ~2~ from the largest blocks, since this is the most efficient, and only use size ~1~ blocks if necessary. This leads to the following greedy algorithm: while the largest block has size ~x > 2~, use a size ~0~ block if there is one (replace ~x,0~ with ~x-2,2~), otherwise use a size ~1~ block (replace ~x,1~ with ~x-1,2~).

The correctness of this greedy algorithm can be proven by finding an explicit function describing the answer. Without size ~0~ blocks, the answer would be ~\sum_{x_i > 2}(x_i-2)~. With arbitrarily many size ~0~ blocks, we can save up to ~\sum_{x_i > 2} \lfloor \frac{x-2}{2} \rfloor~ reversals by cutting off ~2~ at a time instead of ~1~. Thus, we conjecture that the answer is ~f(S) = \sum_{x_i > 2}(x_i-2) - \min\left(\sum_{x_i > 2} \lfloor \frac{x-2}{2} \rfloor,\text{# 0s among }x_i\right)~. It is straightforward to check that ~f~ can decrease by at most ~1~ per reversal, and the greedy algorithm above gives a way to always decrease ~f~ by ~1~ until a good state is reached, so this is indeed the answer.