C++ 最小化字符重新排列的次数，使所有给定的字符串相等

目标是确定在给定大小为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

解释

使用提供的三个字符串，无法构成相同的字符串。

示例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;
}