1389 C(a). Good String（规律，构造）

C. Good String

http://codeforces.com/contest/1389/problem/C

题面：

We can define the left cyclic shift of a string t_1, t_2, \dots, t_n as the operation that results in the string t_2, t_3, \dots, t_n, t_1.

Similarly, we can refer to the right circular shift of a string t as the string t_n t_1 t_2 t_3 \dots t_{n - 1}.

Suppose a string t is considered good when a string's left and right cyclic shifts are identical.

You are given string s which consists of digits 0–9.

What is the smallest possible number of characters you must delete from s so that it becomes a good string?

Input

The first line contains single integer t (1 \le t \le 1000) — the number of test cases.

The next t lines consist of test cases, each on a separate line. For every test case, its first and only line includes the string s, which has a length between 2 and 2\cdot10^5. Every character in the string is a single digit from 0 to 9.

It’s guaranteed that the total length of strings doesn’t exceed 2 \cdot 10^5.

Output

In each test case, calculate the least number of characters needed to delete from s in order to obtain a string that is good.

Example

input

    3
    
    95831
    
    100120013
    
    252525252525
    
    
      
      
      
      
      
      
      
    
    AI写代码

output

    3
    
    5
    
    0
    
    
      
      
      
      
      
    
    AI写代码

Note

In the first test case, it is possible to delete any set of three characters. To illustrate, one could choose to remove the first, third, and fourth positions. Upon deletion of these characters, the resulting string will be '51', which is favorable.

During the second test scenario, it is possible to delete all characters except those with a value of zero: the resulting string consists entirely of zeros, which proves effective.

In the third test case, the given string s is already good.

翻译：

我们将 t_{i=1}^{n} 的左循环移位定义为将字符串的第一个字符移到末尾得到的新字符串。相应地将 t_{i=n}^{i=1} 定义为该操作的逆过程即右循环移位。

我们称其为满足特定条件的一种特殊字符串类型。

你将被给予（得到）字符串 s, 由 数字 0-9组成。(consists of s，由什么组成)。

你需要使 s 变成一个 good 字符串 抹除 (erase) 的最少字符串是什么。

保证 (guaranteed) 字符串的总 (total) 长度 不超过 (exceed ) 2 \cdot 10^5.

题意：

将字符串的头部放到最后，形成新的字符串。

将字符串的尾部放到开头，形成新的字符串。

如果这两个字符串相等，则称是好的字符串。

给你一个字符串，判断删除最少的字符使得字符串变成好的字符串。

题解：

只有两种可能

1. 字符串中字符全部相等。
2. 由 ababab 这样的组成。

代码：

    #include <bits/stdc++.h>
    using namespace std;
    #define ll long long
    
    int main()
    {
    
    int T;
    cin >> T;
    while (T--)
    {
        string s;
        cin >> s;
    		
        int n = (int)s.length();
        for (int i = 0; i < n; i++)//转换这里可以学习
            s[i] -= '0';
    		/*
    			输入的字符123，转换为数字123.
    		*/
    
        int result = n;
    
        for (int a = 0; a < 10; a++)
    		{
            for (int b = 0; b < 10; b++)
            {
                int res = 0;
                bool x = true;
                for (int i = 0; i < n; i++)
                {
                    if ((x && s[i] == a) || (!x && s[i] == b))
                    {
                        res++;
                        x = !x;
                    }
                }
    
    				if(a == b)
    				{
    					result = min(result, n - res);
    				}
    				else
    				{
    					if (res % 2 != 0)
    					res--;
    
    					result = min(result, n - res);
    				}
            }
    		}
        cout << result << endl;
    }
    
    return 0;
    }
    
    
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
    
    AI写代码