CF1660C Get an Even String

如果一个字符串 $a=a_1a_2\dots a_n$ 可以由若干长度为 $2$ 且字符相同的子串拼接而成，则称该字符串为偶字符串。换句话说，字符串 $a$ 满足以下两个条件时被称为偶字符串： - 其长度 $n$ 是偶数； - 对于所有奇数 $i$（$1 \le i \le n - 1$），都有 $a_i = a_{i+1}$。 例如，以下字符串是偶字符串：""（空串）、"tt"、"aabb"、"oooo" 和 "ttrrrroouuuuuuuukk"。以下字符串不是偶字符串："aaa"、"abab" 和 "abba"。 给定一个仅由小写拉丁字母组成的字符串 $s$。请你求出最少需要删除多少个字符，才能使 $s$ 变成偶字符串。被删除的字符不要求连续。

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 接下来是 $t$ 个测试用例的描述。 每个测试用例包含一个字符串 $s$（$1 \le |s| \le 2 \cdot 10^5$），其中 $|s|$ 表示字符串 $s$ 的长度。字符串 $s$ 仅包含小写拉丁字母。 保证所有测试用例中字符串长度之和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示最少需要删除多少个字符，才能使 $s$ 变成偶字符串。

在第一个测试用例中，可以删除下标为 $6$、$7$ 和 $9$ 的字符，使字符串变为偶字符串 "aabbddcc"。 在第二个测试用例中，每个字符都只出现一次，因此要使其变为偶字符串，必须删除字符串中的所有字符。 在第三个测试用例中，可以通过删除第 $4$ 和第 $6$ 个字符得到偶字符串 "aaaabb"，或者删除第 $5$ 个字符和前三个中的任意一个，得到偶字符串 "aabbbb"。 由 ChatGPT 4.1 翻译