在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
热门推荐
10 财运虎年祝福语简短语
11 单亲爸爸春节祝福语简短
12 狗狗上厕所训练
13 植物种植祝福语简短
14 翻译考试祝福语朋友简短
15 个人周年庆简短祝福语
16 狗狗怎么训练
17 分别祝福语简短搞笑英文
18 生日广州男生祝福语简短