Kevin and Binary String (Hard Version)
Contest: IAEPC Preliminary Contest (Codeforces Round 999, Div. 1 + Div. 2)
Difficulty rating: 3500
Tags: data structures, dp

This is the hard version of the problem. The difference between the versions is that in this version, string $$$t$$$ consists of '0', '1' and '?'. You can hack only if you solved all versions of this problem.

Kevin has a binary string $$$s$$$ of length $$$n$$$. Kevin can perform the following operation:

- Choose two adjacent blocks of $$$s$$$ and swap them.

A block is a maximal substring$$$^{\text{∗}}$$$ of identical characters. Formally, denote $$$s[l,r]$$$ as the substring $$$s_l s_{l+1} \ldots s_r$$$. A block is $$$s[l,r]$$$ satisfying:

- $$$l=1$$$ or $$$s_l\not=s_{l-1}$$$.
- $$$s_l=s_{l+1} = \ldots = s_{r}$$$.
- $$$r=n$$$ or $$$s_r\not=s_{r+1}$$$.

Adjacent blocks are two blocks $$$s[l_1,r_1]$$$ and $$$s[l_2,r_2]$$$ satisfying $$$r_1+1=l_2$$$.

For example, if $$$s=\mathtt{000}\,\mathbf{11}\,\mathbf{00}\,\mathtt{111}$$$, Kevin can choose the two blocks $$$s[4,5]$$$ and $$$s[6,7]$$$ and swap them, transforming $$$s$$$ into $$$\mathtt{000}\,\mathbf{00}\,\mathbf{11}\,\mathtt{111}$$$.

Given a string $$$t$$$ of length $$$n$$$ consisting of '0', '1' and '?', Kevin wants to determine the minimum number of operations required to perform such that for any index $$$i$$$ ($$$1\le i\le n$$$), if $$$t_i\not=$$$ '?' then $$$s_i=t_i$$$. If it is impossible, output $$$-1$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a string $$$s$$$ consisting of '0' and '1'.

The second line of each test case contains a string $$$t$$$ consisting of '0', '1' and '?'.

It is guaranteed that the lengths of $$$s$$$ and $$$t$$$ are the same.

It is guaranteed that the sum of the length of $$$s$$$ over all test cases will not exceed $$$4\cdot 10^5$$$.

Output format:
For each test case, output one integer — the minimum number of operations required. If it is impossible, output $$$-1$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case of the first example, the possible way is shown in the statement.

In the second test case of the first example, one possible way could be:

- Swap blocks $$$[2, 2], [3, 3]$$$, $$$s$$$ will become $$$\mathtt{001101}$$$.
- Swap blocks $$$[3, 4], [5, 5]$$$, $$$s$$$ will become $$$\mathtt{000111}$$$.
- Swap blocks $$$[1, 3], [4, 6]$$$, $$$s$$$ will become $$$\mathtt{111000}$$$.

In the first test case of the second example, one possible way could be:

- Swap blocks $$$[1, 1], [2, 2]$$$, $$$s$$$ will become $$$\mathtt{100101}$$$.
- Swap blocks $$$[4, 4], [5, 5]$$$, $$$s$$$ will become $$$\mathtt{100011}$$$.

Example input:
6
0001100111
0000011111
010101
111000
0101
0110
0101
1010
011001
001110
0
1

Example output:
1
3
1
-1
-1
-1

Example input:
6
010101
?0?0??
0101
?0?0
11100101
????????
11100101
???11?1?
1000100011
?11?000?0?
10101
?1011

Example output:
2
-1
0
2
2
-1

Editorial:
First, we divide the string $$$s$$$ into blocks.
Let's analyze the properties of the blocks in $$$s$$$ that do not move (to simplify corner cases, we can add a block with a different number at both ends of $$$s$$$):
• These blocks must alternate between $$$0$$$ and $$$1$$$.
• Between two immovable blocks, the $$$0$$$s will shift toward the same side as the adjacent block of $$$0$$$s, and the $$$1$$$s will shift toward the same side as the adjacent block of $$$1$$$s. For example, $$$\mathtt{0100101101}$$$ will become $$$\mathtt{0000011111}$$$ after the shifting process.
This properties can be proven by induction.
—
Easy Version
For the easy version, since the target string $$$t$$$ is known, we can greedily determine whether each block in $$$s$$$ can remain immovable.
Specifically:
For each block and the previous immovable block, check if the corresponding digits are different. Also, ensure that the numbers in the interval between the two blocks meet the conditions (i.e., the $$$0$$$s and $$$1$$$s in this interval must shift to their respective sides). This can be solved efficiently using prefix sums.
If there are $$$x$$$ blocks between two immovable blocks, then $$$\frac{x}{2}$$$ moves are required.
Time complexity: $$$O(n)$$$.
—
Hard Version
For the hard version, we use dynamic programming to determine which blocks can remain immovable.
Let $$$dp(i)$$$ represent the minimum cost for the $$$i$$$-th block to remain immovable. We have:
$$$$$$dp(i) = \min_{0\leq j <i, (j, i) \text{ is valid}} (dp(j) + (i - j - 1) / 2).$$$$$$
Without loss of generality, assume that the $$$i$$$-th block is composed of $$$0$$$s.
Let the distance between the $$$i$$$-th block and the nearest preceding $$$1$$$-block be $$$p$$$. The number of $$$0$$$s between blocks $$$j$$$ and $$$i$$$ cannot exceed $$$p$$$. There is a restriction: $$$j \geq l_i$$$.
Similarly, for $$$j$$$, we can derive a symmetric restriction: $$$i \leq r_j$$$.
We can use a segment tree to maintain the values of $$$2dp(j) - j$$$ for all valid $$$j$$$. Specifically:
• For a position $$$j$$$, if the current $$$i > r_j$$$, update the corresponding value to $$$+\infty$$$.
• For each $$$i$$$, query the segment tree over the valid interval to compute the minimum efficiently.
Time complexity: $$$O(n \log n)$$$.