在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
热门推荐
8 甄嬛传祝福语简短
10 毕业祝福语简短英语小学
11 祝福语生日男朋友简短
12 毕业祝福语简短给同学
13 年底拜年祝福语大全简短
14 新年恋人祝福语简短创意
15 老师新婚快乐祝福语简短
16 送花简短有内涵祝福语
17 哥哥结婚的祝福语简短
18 老师节祝福语的简短