Codeforces 1389 C. Good String（枚举）

本文主要是介绍Codeforces 1389 C. Good String（枚举），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Let’s call left cyclic shift of some string 𝑡1𝑡2𝑡3…𝑡𝑛−1𝑡𝑛 as string 𝑡2𝑡3…𝑡𝑛−1𝑡𝑛𝑡1.

Analogically, let’s call right cyclic shift of string 𝑡 as string 𝑡𝑛𝑡1𝑡2𝑡3…𝑡𝑛−1.

Let’s say string 𝑡 is good if its left cyclic shift is equal to its right cyclic shift.

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

What is the minimum number of characters you need to erase from 𝑠 to make it good?

Input
The first line contains single integer 𝑡 (1≤𝑡≤1000) — the number of test cases.

Next 𝑡 lines contains test cases — one per line. The first and only line of each test case contains string 𝑠 (2≤|𝑠|≤2⋅105). Each character 𝑠𝑖 is digit 0–9.

It’s guaranteed that the total length of strings doesn’t exceed 2⋅105.

Output
For each test case, print the minimum number of characters you need to erase from 𝑠 to make it good.

Example
inputCopy
3
95831
100120013
252525252525
outputCopy
3
5
0
Note
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.

In the second test case, we can erase all characters except 0: the remaining string is 0000 and it’s good.

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

题意：
求最少删除多少个字符，使得字符串左旋一次右旋一次相同（具体见题意）

思路：
最后肯定变成ABABAB形式
所以枚举AB就好了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>using namespace std;const int maxn = 2e5 + 7;char s[maxn];int main() {int T;scanf("%d",&T);while(T--) {scanf("%s",s + 1);int n = strlen(s + 1);int ans = n - 2;for(int i = 0;i <= 9;i++) {for(int j = 0;j <= 9;j++) {int now = i;int cnt = 0;for(int k = 1;k <= n;k++) {if(s[k] - '0' == now) {if(now == i) now = j;else now = i;} else {cnt++;}}if(now == i) {ans = min(ans,cnt);}}}printf("%d\n",ans);}return 0;
}