C++ 中实现回文排列的最小删除量
c++server side programmingprogramming
问题描述
给定一个字符串 S，我们需要找到可以删除的最小字符数，以使字符串 S 的任意排列成为回文
示例
如果 str = “abcdba”，则我们删除 1 个字符，即 ‘c’或"d"。
算法
1. 回文串有两种类型:偶数长度回文串和奇数长度回文串。 2. 我们可以推断，偶数长度回文串中每个字符出现的次数必须是偶数。 3. 奇数回文串中，除了一个字符出现奇数次外，其他所有字符出现的次数都必须是偶数。 4. 检查每个字符的频率，然后统计出现奇数次的字符。结果是奇数频率字符的总数减 1。
示例
#include <bits/stdc++.h>
#define MAX 26
using namespace std;
int minCharactersRemoved(string str) {
int hash[MAX] = {0};
for (int i = 0; str[i]; ++i) {
hash[str[i] - 'a']++;
}
int cnt = 0;
for (int i = 0; i < MAX; ++i) {
if (hash[i] & 1) {
++cnt;
}
}
return (cnt == 0) ? 0 : (cnt - 1);
}
int main(){
string str = "abcdba";
cout << "Minimum characters to be removed = " <<
minCharactersRemoved(str) << endl;
return 0;
}
编译并执行上述程序，将生成以下输出
输出
Minimum characters to be removed = 1
