---

26. 不相同的字符串（第一期模拟笔试）

原创 已于 2023-10-16 17:16:33 修改 · 粉丝可见 · 172 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132790907

链接： 卡码网KamaCoder

题目：

样例：

cobol<br/>1<br/>abab<br/>

2

思路：

这里的题目要求我们要最少操作删除次数，我们可以先统计每个字符个数，然后开始删除，每操作删除一次，就会产生一个新字符，ans+= r[i] >> 1  就是我们操作次数，然后记得操作过后剩余的字符个数是多少，最后统计一下我们操作完成后，剩余的有多少个 0 位，然后判断我们 产生 ans 个字符后可不可以补完，不可以就累加我们之后继续多余的操作数，就是我们最少操作数。

代码详解如下：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
#define endl '\n'
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
 
string s;
inline void solve()
{
	cin >> s;
	
	vector<int>r(26,0);	// 记录字符个数
	
	for(auto i : s)
	{
		++r[i - 'a'];	// 开始统计
	}
	
	int ans = 0;	// 最少操作次数
	int cnt = 0;	// 记录字符个数是 0 的总数
	
	// 遍历 26 个字母字符
	for(int i = 0;i < 26;++i)
	{
		// 如果有字符超过 1 了，那么开始删除
		if(r[i] > 1)
		{
			// 累加删除操作次数
			ans += r[i] >> 1;
			
			// 计算删除后的字符个数
			r[i] = r[i] - ((r[i] >> 1) << 1);
		}
	}
	
	// 统计 删除过后字符个数是 0 的有多少个
	for(int i = 0;i < 26;++i)
	{
		if(!r[i]) ++ cnt;
	}
	
	// 如果删除两个字符产生的新字符超过 空余字符个数的
	// 这里 ans - cnt 是补 0 位后剩余，
	// 然后就是我们拿两个删 补一个的操作次数，加上我们之前的操作次数 ans 
	if(ans > cnt) ans = ans + (ans - cnt);
	
	// 输出答案
	cout << ans << endl;
}
 
 
signed main()
{
//	freopen("a.txt", "r", stdin);
	___G;
	int _t = 1;
	cin >> _t;
	while (_t--)
	{
		solve();
	}
 
	return 0;
}

最后提交：