Modifiez la chaîne en insérant des caractères pour que chaque sous-chaîne de longueur K ne contienne que des caractères uniques

Lors du traitement des chaînes, une tâche courante consiste à s'assurer que la chaîne répond à certaines conditions. L'une des conditions pourrait être de garantir que chaque sous-chaîne de longueur K dans la chaîne ne contienne que des caractères uniques. Il s'agit d'une exigence courante dans les problèmes liés au codage des données, à la manipulation de chaînes et à la cryptographie.

Énoncé du problème

Le problème que nous essayons de résoudre peut être énoncé comme suit -

Étant donné une chaîne str et un entier K, modifiez la chaîne en insérant des caractères afin que chaque sous-chaîne de longueur K dans la chaîne ne contienne que des caractères uniques.

Solutions suggérées

Nous pouvons résoudre ce problème en utilisant la technique de la fenêtre glissante, qui est une méthode permettant de vérifier efficacement les propriétés de sous-tableaux ou de sous-chaînes consécutifs dans un tableau ou une chaîne plus grande.

Développons les étapes de cet algorithme -

• Initialisez un unordered_map (hashmap) vide pour suivre la fréquence des caractères dans la sous-chaîne actuelle.

• Parcourez les caractères de la chaîne à l'aide d'une fenêtre coulissante de taille K.

• Si un caractère est déjà dans le hashmap, insérez un nouveau caractère jusqu'à ce qu'un caractère unique soit obtenu ou que la taille de la fenêtre coulissante soit K.

• Déplacez la fenêtre coulissante d'un caractère et répétez le processus jusqu'à ce que vous atteigniez la fin de la chaîne.

La complexité temporelle de cet algorithme est O(n), où n est la longueur de la chaîne. En effet, nous parcourons chaque caractère de la chaîne une seule fois.

La traduction chinoise de

Exemple

est :

Exemple

Regardons le code C++ qui implémente l'algorithme ci-dessus -

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

string modifyString(string str, int K) {
   int n = str.size();
   string result = "";
   for(int i = 0; i < n; i++) {
      unordered_map<char, int> freq;
      int j = i;
      while(j < n && j < i + K) {
         while(j < n && freq[str[j]]) {
               result += 'a' + (rand() % 26); // insert a random character
         }
         freq[str[j++]]++;
         result += str[j];
      }
      i = j - 1;
   }
   return result;
}

int main() {
   string str = "abcabc";
   int K = 3;
   cout << modifyString(str, K) << endl;
   return 0;
}

Sortie

bcabc

Ce code insérera aléatoirement une lettre anglaise minuscule lorsqu'il rencontrera des caractères répétés.

Exemple de cas de test

Prenons un exemple pour mieux comprendre cette problématique.

Considérez la chaîne str = "abcabc" et K = 3.

Après avoir exécuté le code, vous pouvez obtenir des résultats similaires à abcxyzabc. Les sous-chaînes de trois caractères sont abc, bcx, cxy, xyz, yza, zab, abc, qui contiennent toutes des caractères uniques.

REMARQUE− Les résultats peuvent varier car nous insérons des caractères aléatoires.

Conclusion

En résumé, cet algorithme fournit un moyen de modifier une chaîne pour garantir que chaque sous-chaîne de longueur K possède des caractères uniques. Il s’agit d’une solution efficace qui exploite la puissance de la technologie des fenêtres coulissantes et la flexibilité du C++. Nous vous encourageons à expérimenter différentes chaînes et valeurs K pour bien saisir ce concept.

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!