在C ++中进行回文排列最少的最小移除
问题陈述
给定字符串S，我们必须找到可以删除的最少字符，以使字符串S的任何排列都成为回文
示例
如果str=“abcdba”，则我们将其删除为1字符，即“c”或“d”。
演算法
1. There can be two types of a palindrome, even length, and odd length palindromes 2. We can deduce the fact that an even length palindrome must have every character occurring even number of times 3.An odd palindrome must have every character occurring even number of times except one character occurring odd number of time 4. Check the frequency of every character and those characters occurring odd number of times are then counted. Then the result is total count of odd frequency characters’ minus 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