Minimiser le nombre de réarrangements de caractères qui rendent toutes les chaînes données égales

Le but ici est de déterminer si toutes les chaînes peuvent être rendues identiques étant donné un nombre arbitraire d'opérations sur un tableau de chaînes Str de taille n. N'importe quel élément peut être retiré d'une chaîne et réinséré n'importe où dans la même chaîne ou dans une autre, le tout en une seule action. Renvoie "Oui" si les chaînes peuvent être rendues égales, "Non" sinon, donnant le nombre minimum d'opérations requises.

Énoncé du problème

Implémentez un programme pour minimiser le nombre de fois où les caractères sont réorganisés afin que toutes les chaînes données soient égales

Exemple Exemple 1

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

The output obtained : Yes 6

Explication

Les trois chaînes fournies dans le tableau Str peuvent être transformées en la même chaîne mno avec un minimum de 6 opérations.

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

Exemple exemple 2

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

The output obtained: No

Explication

En utilisant le tableau de chaînes Str fourni, la même chaîne ne peut pas être générée.

Exemple Exemple 3

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

The output obtained : Yes 4

Explication

Les trois chaînes du tableau Str fourni peuvent être transformées en la même chaîne xyz avec au moins 4 opérations.

Méthode de solution

Pour minimiser le nombre de redimensionnement des caractères afin de rendre toutes les chaînes données égales, nous utilisons la méthode suivante.

La solution à ce problème est de minimiser le nombre de repositionnements de caractères afin que toutes les chaînes données soient égales

L'objectif de rendre toutes les chaînes égales peut être atteint si les lettres sont réparties uniformément dans toutes les chaînes. Autrement dit, la fréquence de chaque caractère du tableau doit être divisible par un nombre de taille « n ».

Algorithme

L'algorithme de repositionnement minimum des caractères requis pour rendre toutes les chaînes données égales est le suivant

• Étape 1 − Démarrer

• Étape 2 - Définir une fonction pour vérifier si les chaînes peuvent devenir identiques

• Étape 3 - Définissez un tableau pour stocker les fréquences de tous les caractères. Ici, nous définissons « fre ».

• Étape 4 - Parcourez le tableau de chaînes fourni.

• Étape 5 - Parcourez chaque caractère de la chaîne Str donnée.

• Étape 6 - Mettre à jour la fréquence obtenue

• Étape 7 - Vérifiez maintenant les caractères de chaque lettre

• Étape 8 - Si la fréquence n'est pas divisible par un nombre de taille n, inscrivez "Non"

• Étape 9 - Divisez la fréquence de chaque caractère par la taille n

• Étape 10 - Définissez une variable entière "résultat" et stockez le résultat comme le nombre minimum d'opérations

• Étape 11 - Stockez la fréquence de chaque caractère dans la chaîne d'origine "org"

• Étape 12 - Obtenez également le nombre de caractères supplémentaires

• Étape 13 - Imprimez Oui et le résultat obtenu.

• Étape 14 − Arrêtez

Exemple : programme C

Il s'agit d'une implémentation de programme C de l'algorithme ci-dessus pour minimiser le nombre de caractères de repositionnement afin que toutes les chaînes données soient égales.

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

Sortie

Yes 6

Conclusion

De même, nous pouvons minimiser le nombre de repositionnements de caractères pour rendre toutes les chaînes données égales.

Dans cet article, le défi consistant à obtenir un programme permettant de minimiser le nombre de repositionnements de caractères pour rendre toutes les chaînes données égales est abordé.

Un code de programmation et des algorithmes C sont fournis pour minimiser le nombre de réarrangements de caractères afin que toutes les chaînes données soient égales.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!