CF2254C2 Marenol (hard version)

这是本题的难度较高版本。在本版本中，你需要求出将 $a$ 变换为 $b$ 所需的最少操作次数。 Yousef 给了你两个长度相同的二进制字符串 $a$ 和 $b$。 你可以进行以下任意操作： - 选择 $a$ 中的某个子串$^*$，如果它等于 $\texttt{001}$，则可以将其替换为 $\texttt{100}$，反之亦然（即 $\texttt{001} \rightarrow \texttt{100}$ 或 $\texttt{100} \rightarrow \texttt{001}$）。 - 选择 $a$ 中的某个子串，如果它等于 $\texttt{110}$，则可以将其替换为 $\texttt{011}$，反之亦然（即 $\texttt{011} \rightarrow \texttt{110}$ 或 $\texttt{110} \rightarrow \texttt{011}$）。 你的任务是求出将字符串 $a$ 变换为字符串 $b$ 所需的最少操作次数。如果无法通过上述操作将 $a$ 变换为 $b$，则输出 $-1$。 $^*$字符串 $a$ 是字符串 $b$ 的一个子串，如果 $a$ 可以通过删除 $b$ 的若干（可能为零或所有）前缀和若干（可能为零或所有）后缀字符得到。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示每个字符串的长度。 每个测试用例的第二行包含一个二进制字符串 $a$（$|a| = n$），字符串中仅包含字符 $\texttt{0}$ 和/或 $\texttt{1}$。 每个测试用例的第三行包含一个二进制字符串 $b$（$|b| = n$），字符串中仅包含字符 $\texttt{0}$ 和/或 $\texttt{1}$。 保证所有测试用例中 $n$ 之和不超过 $2 \cdot 10^5$。

每组测试用例输出一行，表示将 $a$ 变换为 $b$ 所需的最少操作次数。如果无法完成变换，则输出 $-1$。

在第一个测试用例中，我们可以选择子串 $a[2, 4]=\texttt{100}$，将其替换为 $\texttt{001}$。这仅需 $1$ 次操作。 在第二个测试用例中，无法将 $a$ 变换为 $b$，因此答案为 $-1$。 在第三个测试用例中，我们可以按照以下步骤操作： - $\texttt{1}\ {\color{blue}{\texttt{100}}}\ \texttt{00}\ \rightarrow\ \texttt{1}\ {\color{blue}{\texttt{001}}}\ \texttt{00}$ - $\texttt{100}\ {\color{blue}{\texttt{100}}}\ \rightarrow\ \texttt{100}\ {\color{blue}{\texttt{001}}}$ - ${\color{blue}{\texttt{100}}}\ \texttt{001}\ \rightarrow\ {\color{blue}{\texttt{001}}}\ \texttt{001}$ - $\texttt{00}\ {\color{blue}{\texttt{100}}}\ \texttt{1}\ \rightarrow\ \texttt{00}\ {\color{blue}{\texttt{001}}}\ \texttt{1}$ 共需 $4$ 次操作。并且可以证明 $4$ 是最少的操作次数。 由 ChatGPT 5 翻译