这是问题的困难版本。版本之间的区别在于,在此版本中,字符串$$$t$$$ 由'0'、'1' 和'?' 组成。只有解决了该问题的所有版本,您才能破解。
Kevin 有一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$。 Kevin 可以执行以下操作:
- 选择 $$$s$$$ 的两个相邻块并交换它们。
块是相同字符的最大子串$$$^{\text{*}}$$$。形式上,将 $$$s[l,r]$$$ 表示为子字符串 $$$s_l s_{l+1} \ldots s_r$$$。一个块是 $$$s[l,r]$$$ 满足:
- $$$l=1$$$ 或 $$$s_l\not=s_{l-1}$$$。
- $$$s_l=s_{l+1} = \ldots = s_{r}$$$。
- $$$r=n$$$ 或 $$$s_r\not=s_{r+1}$$$。
相邻块是满足 $$$r_1+1=l_2$$$ 的两个块 $$$s[l_1,r_1]$$$ 和 $$$s[l_2,r_2]$$$。
例如,如果 $$$s=\mathtt{000}\,\mathbf{11}\,\mathbf{00}\,\mathtt{111}$$$,Kevin 可以选择两个块 $$$s[4,5]$$$ 和 $$$s[6,7]$$$ 并交换它们,将 $$$s$$$ 转换为$$$\mathtt{000}\,\mathbf{00}\,\mathbf{11}\,\mathtt{111}$$$。
给定一个长度为 $$$n$$$ 的字符串 $$$t$$$,由 '0'、'1' 和 '?' 组成,Kevin 希望确定执行所需的最小操作数,使得对于任何索引 $$$i$$$ ($$$1\le i\le n$$$),如果 $$$t_i\not=$$$ '?'那么$$$s_i=t_i$$$。如果不可能,则输出$$$-1$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个由“0”和“1”组成的字符串$$$s$$$。
每个测试用例的第二行包含一个由“0”、“1”和“?”组成的字符串$$$t$$$。
保证$$$s$$$ 和$$$t$$$ 的长度相同。
保证所有测试用例$$$s$$$的长度总和不会超过$$$4\cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数——所需的最少操作数。如果不可能,则输出$$$-1$$$。
示例
输入 #1
6 0001100111 0000011111 010101 111000 0101 0110 0101 1010 011001 001110 0 1
输出 #1
1 3 1 -1 -1 -1
输入 #2
6 010101 ?0?0?? 0101 ?0?0 11100101 ???????? 11100101 ???11?1? 1000100011 ?11?000?0? 10101 ?1011
输出 #2
2 -1 0 2 2 -1
注意
在第一个示例的第一个测试用例中,语句中显示了可能的方式。
在第一个示例的第二个测试用例中,一种可能的方法是:
- 交换块 $$$[2, 2], [3, 3]$$$, $$$s$$$ 将变为 $$$\mathtt{001101}$$$。
- 交换块 $$$[3, 4], [5, 5]$$$, $$$s$$$ 将变为 $$$\mathtt{000111}$$$。
- 交换块 $$$[1, 3], [4, 6]$$$, $$$s$$$ 将变为 $$$\mathtt{111000}$$$。
在第二个示例的第一个测试用例中,一种可能的方法是:
- 交换块 $$$[1, 1], [2, 2]$$$, $$$s$$$ 将变为 $$$\mathtt{100101}$$$。
- 交换块 $$$[4, 4], [5, 5]$$$, $$$s$$$ 将变为 $$$\mathtt{100011}$$$。