codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.