CF1616E Lexicographically Small Enough

给定两个长度相等为 $n$ 的字符串 $s$ 和 $t$。每次操作，你可以交换字符串 $s$ 中任意两个相邻的字符。 你需要求出将字符串 $s$ 变为字典序小于字符串 $t$ 所需的最少操作次数。 如果满足以下任一条件，则字符串 $a$ 的字典序小于字符串 $b$： - $a$ 是 $b$ 的前缀，且 $a \ne b$； - 在 $a$ 和 $b$ 第一个不同的位置，$a$ 的字母在字母表中比 $b$ 的对应字母更靠前。

输入的第一行包含一个整数 $q$（$1 \le q \le 10\,000$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$）。 每个测试用例的第二行包含一个由 $n$ 个小写英文字母组成的字符串 $s$。 每个测试用例的第三行包含一个由 $n$ 个小写英文字母组成的字符串 $t$。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一行，表示将字符串 $s$ 变为字典序小于字符串 $t$ 所需的最少操作次数。如果无法做到，输出 $-1$。

由 ChatGPT 4.1 翻译