1389C.md (1541B)
1 Source: https://codeforces.com/problemset/problem/1389/C 2 3 C. Good String 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Let's call left cyclic shift of some string $t_1 t_2 t_3 \dots t_{n - 1} t_n$ as string $t_2 t_3 \dots t_{n - 1} t_n t_1$. 22 23 Analogically, let's call right cyclic shift of string $t$ as string $t_n t_1 t_2 t_3 \dots t_{n - 1}$. 24 25 Let's say string $t$ is good if its left cyclic shift is equal to its right cyclic shift. 26 27 You are given string $s$ which consists of digits 0–9. 28 29 What is the minimum number of characters you need to erase from $s$ to make it good? 30 31 Input 32 33 The first line contains single integer $t$ ($1 \le t \le 1000$) — the number of test cases. 34 35 Next $t$ lines contains test cases — one per line. The first and only line of each test case contains string $s$ ($2 \le |s| \le 2 \cdot 10^5$). Each character $s_i$ is digit 0–9. 36 37 It's guaranteed that the total length of strings doesn't exceed $2 \cdot 10^5$. 38 39 Output 40 41 For each test case, print the minimum number of characters you need to erase from $s$ to make it good. 42 43 Example 44 45 Input 46 47 ``` 48 3 49 95831 50 100120013 51 252525252525 52 ``` 53 54 Output 55 56 ``` 57 3 58 5 59 0 60 ``` 61 62 Note 63 64 In the first test case, you can erase any $3$ characters, for example, the $1$-st, the $3$-rd, and the $4$-th. You'll get string 51 and it is good. 65 66 In the second test case, we can erase all characters except 0: the remaining string is 0000 and it's good. 67 68 In the third test case, the given string $s$ is already good.