CF1385D a-Good String

给定一个由小写拉丁字母组成的字符串 $s[1 \dots n]$。保证 $n = 2^k$，其中 $k \ge 0$。 如果字符串 $s[1 \dots n]$ 满足以下三个条件之一，则称其为 $c$-good 字符串： - $s$ 的长度为 $1$，且唯一的字符为 $c$（即 $s_1 = c$）； - $s$ 的长度大于 $1$，且前一半全为字符 $c$（即 $s_1 = s_2 = \dots = s_{\frac{n}{2}} = c$），并且后一半（即 $s_{\frac{n}{2} + 1}s_{\frac{n}{2} + 2} \dots s_n$）是 $(c+1)$-good 字符串； - $s$ 的长度大于 $1$，且后一半全为字符 $c$（即 $s_{\frac{n}{2} + 1} = s_{\frac{n}{2} + 2} = \dots = s_n = c$），并且前一半（即 $s_1s_2 \dots s_{\frac{n}{2}}$）是 $(c+1)$-good 字符串。 例如："aabc" 是 'a'-good 字符串，"ffgheeee" 是 'e'-good 字符串。 每次操作，你可以选择一个下标 $i$（$1 \le i \le n$），将 $s_i$ 替换为任意一个小写拉丁字母（'a' 到 'z' 之间的任意字符）。 你的任务是，求将 $s$ 变为 'a'-good 字符串（即 $c$-good 字符串，$c = $ 'a'）所需的最少操作次数。保证一定存在解。 你需要回答 $t$ 组独立的测试用例。 另一个 'a'-good 字符串的例子如下。考虑字符串 $s = $ "cdbbaaaa"。它是一个 'a'-good 字符串，因为： - 字符串的后一半 "aaaa" 全为字符 'a'； - 前一半 "cdbb" 是 'b'-good 字符串，因为： - 后一半 "bb" 全为字符 'b'； - 前一半 "cd" 是 'c'-good 字符串，因为： - 前一半 "c" 全为字符 'c'； - 后一半 "d" 是 'd'-good 字符串。

输入的第一行为一个整数 $t$（$1 \le t \le 2 \cdot 10^4$），表示测试用例的数量。接下来有 $t$ 组测试用例。 每组测试用例的第一行为一个整数 $n$（$1 \le n \le 131072$），表示字符串 $s$ 的长度。保证 $n = 2^k$，其中 $k \ge 0$。第二行为一个长度为 $n$ 的字符串 $s$，由小写拉丁字母组成。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$（$\sum n \le 2 \cdot 10^5$）。

对于每组测试用例，输出一个整数，表示将 $s$ 变为 'a'-good 字符串所需的最少操作次数。保证一定存在解。

由 ChatGPT 4.1 翻译