C. Good String(暴力枚举)

Problem - 1389C - Codeforces

题意:

我们把某个字符串t1t2t3...tn-1tn的左循环移位称为字符串t2t3...tn-1tnt1。

类似地，我们把字符串t的右循环移动称为字符串tnt1t2t3...tn-1。

如果字符串t的左循环移位等于其右循环移位，我们就说它是好的。

给你一个由数字0-9组成的字符串s。

你需要从s中擦除多少个字符才能使其成为好字符串？

输入
第一行包含单个整数t（1≤t≤1000）--测试案例的数量。

接下来的t行包含测试用例--每行一个。每个测试用例的第一行也是唯一一行包含字符串s(2≤|s|≤2⋅105)。每个字符si是数字0-9。

保证字符串的总长度不超过2⋅105。

输出
对于每个测试案例，打印你需要从s中删除的最小字符数，以使其成为好的。
题解:
假设我们设这个字符串为奇数,长度为5

原

1 2 3 4 5

2 3 4 5 1

5 1 2 3 4

2 = 5 

3 = 1

4 = 2

5 = 3

1 = 4

我们发现如果长度为奇数,只有所有字母相同的情况下才会出现

接着我们考虑偶数的情况

1 2 3 4 

2 3 4 1

4 1 2 3

2 = 4

3 = 1

4 = 2

1 = 3

发现只有下标为偶数时都相等,为奇数时都相等才行;

为偶数时会有两种不同数字(相同的奇数n为奇数已经考虑了)

那么我们暴力枚举所有(奇数位,偶数位)为两种数字的情况

时间复杂度为9*9*2e5发现可以过

#include<iostream>
#include<cstring>
#include<map> 
#include<algorithm>
using namespace std;
int n;
char a[200050];
int len1(int x,int y)
{
	char o = x+'0';
	char p = y+'0';
	int f = 0;
	int cnt = 0;
	for(int i = 1;i <= n;i++)
	{
		if(a[i]==o&&f == 0)
		{
			f^=1;
		}
		if(a[i]==p&&f == 1)
		{
			f^= 1;
			cnt += 2;
		}
	}
	return cnt;
}
void solve()
{
	cin >> a+1;
	n = strlen(a+1);
	map<int,int> vis;
	int ans = 0;
	for(int i = 1;i <= n;i++)
	{
		vis[a[i]-'0']++;
		ans = max(ans,vis[a[i]-'0']);
	}
	for(int i = 0;i <= 9;i++)
	{
		for(int j = 0;j <= 9;j++)
		{
			if(i == j)
			continue;
			ans = max(ans,len1(i,j));
		}
	}
	cout<<n-ans<<"\n";
}
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		solve();
	}
}