← 返回题目列表

Codeforces · 1821/C

C. 撕开它

中文机器翻译题面 查看原题

给你一个字符串 $$$s$$$,由小写拉丁字母组成。

在一项操作中,您可以选择其中的多个(一个或多个)位置,使得两个选定位置不会彼此相邻。然后从字符串中删除选定位置上的字母。将所得部分连接起来而不改变其顺序。

最少需要多少次运算才能使 $$$s$$$ 中的所有字母都相同?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的唯一行包含一个字符串 $$$s$$$,由小写拉丁字母组成。它的长度是从 $$$1$$$ 到 $$$2 \cdot 10^5$$$。

所有测试用例的字符串总长度不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 使给定字符串 $$$s$$$ 中的所有字母相同所需的最少操作数。

示例

输入 #1

5
abacaba
codeforces
oooooooo
abcdef
mewheniseearulhiiarul

输出 #1

1
3
0
2
4

注意

在第一个测试用例中,您可以选择位置 $$$2、4$$$ 和 $$$6$$$ 并删除相应的字母 'b'、'c' 和 'b'。

在第三个测试用例中,字符串中的字母已经相同,因此您不必进行任何操作。

在第四个测试用例中,$$$2$$$ 操作中可能的解决方案之一如下。您可以先选择位置 $$$1, 4, 6$$$。该字符串变为“bce”。然后选择位置$$$1$$$ 和$$$3$$$。该字符串变为“c”。其中的所有字母都是相同的,因为它只是一个字母。