การลบตัวอักษรน้อยที่สุดเพื่อทำให้ permutation ของสตริงเป็นพาลินโดรมใน C++

ข้อกำหนดโจทย์

กำหนดสตริง S เราต้องหาตัวอักษรน้อยที่สุดที่สามารถลบได้ เพื่อให้ permutation ใดๆ ของสตริง S เป็นพาลินโดรม

ตัวอย่าง

ถ้า str = "abcdba" แล้วเราต้องลบ 1 ตัวอักษร คือ 'c' หรือ 'd'

อัลกอริทึม

1. มีพาลินโดรม 2 ประเภท คือ ความยาวคู่ และ ความยาวคี่
2. เราสรุปได้ว่า พาลินโดรมความยาวคู่ ต้องมีทุกตัวอักษรเกิดขึ้นจำนวนคู่ครั้ง
3. พาลินโดรมความยาวคี่ ต้องมีทุกตัวอักษรเกิดขึ้นจำนวนคู่ครั้ง ยกเว้นตัวอักษรหนึ่งตัวที่เกิดขึ้นจำนวนคี่ครั้ง
4. ตรวจสอบความถี่ของทุกตัวอักษร และนับตัวอักษรที่เกิดขึ้นจำนวนคี่ครั้ง ผลลัพธ์คือ จำนวนตัวอักษรที่มีความถี่คี่ ลบ 1

ตัวอย่างโค้ด C++

#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