Minimize the number of rearrangements of characters that make all given strings equal

The goal here is to determine whether all strings can be made identical given an arbitrary number of operations on a string array Str of size n. Any element can be taken out of a string and put back anywhere in the same or another string, all in one action. Returns "Yes" if the strings can be made equal, "No" otherwise, giving the minimum number of operations required.

Problem Statement

Implement a program to minimize the number of rearrangements of characters so that all given strings are equal

Example Example 1

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

The output obtained : Yes 6

explain

The three strings provided in the array Str can be turned into the same string mno through at least 6 operations.

{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}

Example Example 2

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

The output obtained: No

explain

Using the provided string array Str, the same string cannot be generated.

ExampleExample 3

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

The output obtained : Yes 4

explain

All three strings of the provided array Str can be changed into the same string xyz through at least 4 operations.

Solution method

In order to minimize the number of times of re-sizing characters so that all given strings are equal, we use the following method.

The solution to this problem is to minimize the number of character repositionings so that all given strings are equal

The goal of making all strings equal can be achieved if the letters are evenly distributed among all strings. That is, the frequency of each character in the array needs to be divisible by a number of size "n".

algorithm

The minimum character repositioning algorithm required to make all given strings equal is as follows

• Step 1 − Start

• Step 2 - Define a function to check if the strings can become identical

• Step 3 - Define an array to store the frequencies of all characters. Here we define "fre".

• Step 4 − Traverse the provided string array.

• Step 5 - Iterate through each character of the given string Str.

• Step 6 - Update the obtained frequency

• Step 7 - Now check the characters of each letter

• Step 8 - If the frequency is not divisible by a number of size n, print "No"

• Step 9 - Divide the frequency of each character by the size n

• Step 10 - Define an integer variable "result" and store the result as the minimum number of operations

• Step 11 - Store the frequency of each character in the original string "org"

• Step 12 - Also get the number of extra characters

• Step 13 - Print Yes and the result obtained.

• Step 14 − Stop

Example: C program

This is a C program implementation of the above algorithm for minimizing the number of repositioning characters so that all given strings are equal.

#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;
}

Output

Yes 6

in conclusion

Similarly, we can minimize the number of character repositionings so that all given strings are equal.

In this article, the challenge of obtaining a program to minimize the number of character repositionings to make all given strings equal is addressed.

Provides C programming code and algorithms to minimize the number of rearrangements of characters so that all given strings are equal.

The above is the detailed content of Minimize the number of rearrangements of characters that make all given strings equal. For more information, please follow other related articles on the PHP Chinese website!