Loại bỏ tối thiểu để thực hiện hoán vị palindrome trong C ++

Tuyên bố vấn đề

Cho một chuỗi S, chúng ta phải tìm các ký tự tối thiểu mà chúng ta có thể loại bỏ để biến bất kỳ hoán vị nào của chuỗi S trở thành palindrome

Ví dụ

Nếu str =“abcdba” thì chúng tôi xóa thành 1 ký tự tức là ‘c’or‘ d ’.

Thuật toán

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

Ví dụ

#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;
}

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau

Đầu ra

Minimum characters to be removed = 1