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