C++에서 회문 순열을 만들기 위한 최소 제거

문제 설명

문자열 S가 주어지면 문자열 S의 순열을 회문으로 만들기 위해 제거할 수 있는 최소 문자를 찾아야 합니다.

예시

str ="abcdba"인 경우 'c' 또는 'd'와 같은 1개의 문자로 제거합니다.

알고리즘

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