Nombre minimum d'échanges entre deux chaînes telles qu'une chaîne soit strictement supérieure à l'autre

Dans cet article, nous aborderons un problème intéressant de manipulation de chaînes : "Le nombre minimum d'échanges requis entre deux chaînes de telle sorte qu'une chaîne soit strictement plus grande que l'autre". Nous comprendrons le problème, détaillerons les stratégies pour le résoudre, le mettrons en œuvre en C++ et clarifierons les concepts avec un exemple pertinent.

Comprendre l'énoncé du problème

Étant donné deux chaînes de longueur égale, notre objectif est de déterminer le nombre minimum d'échanges de caractères requis pour rendre une chaîne strictement plus grande que l'autre. Les caractères sont échangés entre les deux chaînes, chaque échange impliquant un caractère des deux chaînes. Les chaînes sont comparées lexicographiquement, où 'a'

Méthode

L'idée est d'utiliser un algorithme glouton. On commence par le début de la chaîne, et pour chaque position, si le caractère de la première chaîne est plus petit que le caractère correspondant de la deuxième chaîne, on les échange. S'ils sont égaux, nous recherchons le caractère le plus grand dans la deuxième chaîne à échanger. Si aucun caractère de ce type n’est trouvé, nous passons à la position suivante. Nous répétons ce processus jusqu'à ce que tous les caractères de la chaîne aient été traités.

Exemple

Implémentons cette approche en C++ -

#include<bits/stdc++.h>
using namespace std;

int minSwaps(string &s1, string &s2) {
   int swaps = 0;
   int n = s1.size();
   for(int i=0; i<n; i++) {
      if(s1[i] < s2[i]) {
         swap(s1[i], s2[i]);
         swaps++;
      }
      else if(s1[i] == s2[i]) {
         for(int j=i+1; j<n; j++) {
               if(s2[j] > s1[i]) {
                  swap(s1[i], s2[j]);
                  swaps++;
                  break;
               }
         }
      }
   }
   return (s1 > s2) ? swaps : -1;
}

int main() {
   string s1 = "bbca";
   string s2 = "abbc";
   int swaps = minSwaps(s1, s2);
   if(swaps != -1)
      cout << "Minimum swaps: " << swaps << "\n";
   else
      cout << "Cannot make string 1 greater\n";
   return 0;
}

Sortie

Minimum swaps: 2

Cas de test

Considérons les chaînes "bbca" et "abbc". L'échange suivant aura lieu −

• Échangez 'b' dans la première chaîne avec 'a' dans la deuxième chaîne. Les chaînes sont désormais « bbac » et « abbc ».

• Échangez "c" dans la première chaîne avec "b" dans la deuxième chaîne. Les chaînes sont désormais "bbcb" et "abac".

"bbcb" est lexicographiquement plus grand que "abac". Par conséquent, le nombre minimum de swaps requis est de 2, et le résultat du programme sera « Nombre minimum de swaps : 2 ».

Conclusion

Dans cet article, nous explorons le problème de la détermination du nombre minimum d'échanges requis entre deux chaînes de telle sorte qu'une chaîne soit lexicographiquement plus grande que l'autre. Nous discutons des stratégies pour résoudre le problème, l'implémentons en C++ et expliquons le concept avec des exemples. Les questions de manipulation de chaînes comme celle-ci sont courantes dans les entretiens et les programmes compétitifs, et comprendre ces concepts est très bénéfique.

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!