← 返回题目列表

Codeforces · 1354/B

B. 三元字符串

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

给定一个字符串 $$$s$$$,其中每个字符都是 1、2 或 3。您必须选择 $$$s$$$ 的最短连续子字符串,使其包含这三个字符中的每一个至少一次。

字符串 $$$s$$$ 的连续子字符串是可以通过从 $$$s$$$ 开头删除一些(可能为零)字符和从 $$$s$$$ 结尾删除一些(可能零)字符来从 $$$s$$$ 获得的字符串。

输入

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

每个测试用例由一行包含字符串 $$$s$$$ ($$$1 \le |s| \le 200000$$$) 组成。保证 $$$s$$$ 的每个字符都是 1、2 或 3。

所有测试用例中所有字符串的长度总和不超过$$$200000$$$。

输出

对于每个测试用例,打印一个整数 - $$$s$$$ 中至少包含一次所有三种类型字符的最短连续子字符串的长度。如果没有这样的子字符串,则打印$$$0$$$。

示例

输入 #1

7
123
12222133333332
112233
332211
12121212
333333
31121

输出 #1

3
3
4
4
0
0
4

注意

考虑示例测试:

在第一个测试用例中,可以使用子字符串 123。

在第二个测试用例中,可以使用子字符串213。

在第三个测试用例中,可以使用子字符串1223。

在第四个测试用例中,可以使用子字符串3221。

在第五个测试用例中,$$$s$$$ 中没有字符 3。

在第六个测试用例中,$$$s$$$ 中没有字符 1。

在第七个测试用例中,可以使用子字符串3112。