最小化字元重新定位次數，使所有給定字串相等

---

此處的目標是確定，給定一個大小為 n 的字串陣列 Str，是否可以在任意數量的操作中使所有字串都相同。任何元素都可以從字串中取出並在同一字串或另一個字串的任何位置放回，所有這些都算作一次操作。如果字串能夠變得彼此相等，則返回“Yes”，否則返回“No”，並附帶所需的最少操作次數。

問題陳述

實現一個程式，以最小化字元重新定位的次數，使所有給定字串相等

示例 1

Let us take the Input: n = 3, 
The input array, Str = {mmm, nnn, ooo}

The output obtained : Yes 6

解釋

陣列 Str 中提供的三個字串都可以以最少 6 次操作變為相同的字串 mno。

{mmm, nnn, ooo} −> {mm, mnnn, ooo}
{mm, mnnn, ooo} −> {m, mnnn, mooo}
{m, mnnn, mooo} −> {mn, mnn, mooo}
{mn, mnn, mooo} −> {mn, mn, mnooo}
{mn, mn, mnooo} −> {mno, mn, mnoo}
{mno, mn, mnooo} −> {mno, mno, mno}

示例 2

Let us take the Input: n = 3, 
The input array, Str = {abc, aab, bbd}

The output obtained: No

解釋

使用陣列 Str 中提供的三個字串，無法構成相同的字串。

示例 3

Let us take the Input: n = 3, 
The input array, Str = {xxy, zzz, xyy}

The output obtained : Yes 4

解釋

陣列 Str 中提供的三個字串都可以以最少 4 次操作變為相同的字串 xyz。

解決方案方法

為了最小化字元重新定位的次數以使所有給定字串相等，我們使用以下方法。

解決這個問題並最小化字元重新定位的次數以使所有給定字串相等的方法

如果字母在所有字串中均勻分佈，則可以實現使所有字串相等的目標。也就是說，字串陣列中每個字元的頻率必須能夠被大小“n”整除。

演算法

最小化字元重新定位次數以使所有給定字串相等的演算法如下所示

• 步驟 1 − 開始

• 步驟 2 − 定義一個函式來檢查字串是否可以變得相同。

• 步驟 3 − 定義一個數組來儲存所有字元的頻率。這裡我們定義為“fre”。

• 步驟 4 − 遍歷提供的字串陣列。

• 步驟 5 − 遍歷給定字串 Str 的每個字元。

• 步驟 6 − 更新獲得的頻率

• 步驟 7 − 現在檢查字母表中的每個字元

• 步驟 8 − 如果頻率不能被大小 n 整除，則列印“No”

• 步驟 9 − 將每個字元的頻率除以大小 n

• 步驟 10 − 定義一個整數變數“result”並將獲得的結果儲存為最小運算元

• 步驟 11 − 將原始字串“org”中每個字元的頻率儲存起來

• 步驟 12 − 獲取額外的字元數量

• 步驟 13 − 列印 Yes 和獲得的結果。

• 步驟 14 − 結束

示例：C 程式

以下是上述演算法的 C 語言程式實現，用於最小化字元重新定位的次數以使所有給定字串相等。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// Define a function to check if the strings could be made identical or not
void equalOrNot(char* Str[], int n){

   // Array fre to store the frequencies of all the characters
   int fre[26] = {0};
   
   // Traverse the provided array of strings
   for (int i = 0; i < n; i++) {
   
      // Traverse each characters of the given string Str
      for (int j = 0; j < strlen(Str[i]); j++){
         // Update the frequencies obtained
         fre[Str[i][j] - 'a']++;
      }
   }
   
   // now check for every character of the alphabet
   for (int i = 0; i < 26; i++){
   
      // If the frequency is not divisible by the size n, then print No.
      if (fre[i] % n != 0){
         printf("No\n");
         return;
      }
   }
   
   // Dividing the frequency of each of the character with the size n
   for (int i = 0; i < 26; i++)
      fre[i] /= n;
      
   // Store the result obtained as the minimum number of operations
   int result = 0;
   for (int i = 0; i < n; i++) {
   
      // Store the frequency of each od the characters in the original string org
      int org[26] = {0};
      for (int j = 0; j < strlen(Str[i]); j++)
         org[Str[i][j] - 'a']++;
         
      // Get the number of additional characters as well
      for (int i = 0; i < 26; i++){
         if (fre[i] > 0 && org[i] > 0){
            result += abs(fre[i] - org[i]);
         }
      }
   }
   printf("Yes %d\n", result);
   return;
}
int main(){
   int n = 3;
   char* Str[] = { "mmm", "nnn", "ooo" };
   equalOrNot(Str, n);
   return 0;
}

輸出

Yes 6

結論

同樣，我們可以最小化字元重新定位的次數，以使所有給定字串相等。

本文解決了獲取程式以最小化字元重新定位次數以使所有給定字串相等的問題。

此處提供了 C 語言程式碼以及最小化字元重新定位次數以使所有給定字串相等的演算法。