需要移除的最小字元數，以便字串可以重新排列形成迴文

---

在這個問題中，我們需要從字串中移除最少的字元，並將剩餘的字元重新排列以使字串成為迴文。

為了解決這個問題，我們首先應該問自己的問題是何時可以使字串成為迴文。在以下兩種情況下，我們可以使字串成為迴文。

• 如果給定字串中每個字元的頻率都是偶數。

• 如果只有一個字元的頻率是奇數，而所有其他字元的頻率都是偶數。

因此，我們需要移除最少的字元以使每個字元的頻率為偶數，除了任何單個字元。

問題陳述 - 我們給定一個包含 N 個小寫字母字元的字串 str。我們需要從給定的字串中移除最少的字元，以便我們可以透過重新排列剩餘的字元來建立一個迴文字串。

示例

Input –  str = "abcabccd"

Output – 1

解釋

這裡，我們需要移除 'c' 或 'd' 字元。

Input –  str = ‘aabbc’

Output – 0

解釋

我們不需要移除任何字元，因為我們可以從給定的字串中建立一個 'abcba' 迴文字串。

Input –  str = ‘pqrstvu’

Output – 6

解釋

為了使給定的字串成為迴文，我們必須移除所有字元，除了一個。我們只能使用此字串建立一個長度為 1 的迴文字串。

方法 1

在這種方法中，我們將計算給定字串中每個字元的頻率。之後，我們將計算頻率為奇數的字元總數。我們需要只保留一個頻率為奇數的字元，並移除其他字元以使其頻率為偶數。

演算法

• 步驟 1 - 定義長度等於 26 的 'freq' 陣列。

• 步驟 2 - 使用 memset() 方法將所有陣列元素初始化為 0。

• 步驟 3 - 遍歷字串並在 'freq' 陣列中儲存每個字元的頻率。

• 步驟 4 - 將 'cnt' 變數初始化為 0。

• 步驟 5 - 現在，遍歷 'freq' 陣列，如果陣列中當前索引處的值為奇數，則將 'cnt' 的值增加 1。

• 步驟 6 - 如果 'cnt' 變數的最終值為 0 或 1，則返回 0。

• 步驟 7 - 返回 'cnt – 1'，因為我們可以保留一個頻率為奇數的字元。

示例

#include <bits/stdc++.h>
using namespace std;
// function to find the minimum number of deletions required to make string palindrome
int deletionCount(string str){    
   int fre[26]; // array of size 26, which stores the frequency of each character
   memset(fre, 0, sizeof(fre));     // Initialize array with 0
   int n = str.size();
   
   // cnt frequency of each character in the string
   for (int i = 0; i < n; i++){
      fre[str[i] - 'a'] += 1;
   }
   int cnt = 0;
   
   // find the number of characters with odd frequency
   for (int i = 0; i < 26; i++){
      if (fre[i] % 2){
         cnt += 1;
      }
   }
   
   // If characters with odd frequency are 0 or 1, then the string can be palindrome without any character deletion
   if (cnt == 0 || cnt == 1){
      return 0;
   }
   
   // Otherwise, return cnt - 1, as one character can be odd
   else{
      return cnt - 1;
   }
}
int main(){
   string str = "abcabccd";
   cout << "The minimum number of deletions of characters required to make string palindrome is - " << deletionCount(str) << endl;
}

輸出

The minimum number of deletions of characters required to make string palindrome is - 1

時間複雜度 - O(N)，因為我們計算給定字串中每個字元的頻率。

空間複雜度 - O(1)，因為我們使用常數空間。

結論

我們學習瞭如何找到排列剩餘字元以形成迴文字串所需的最小字元移除數。我們使用 'freq' 陣列來儲存每個字元的頻率，但使用者也可以使用 count() 方法來計算給定字串中特定字元的頻率。