最小化字符重新定位次数，使所有给定字符串相等

---

此处的目标是确定，给定一个大小为 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 语言代码以及最小化字符重新定位次数以使所有给定字符串相等的算法。