Programme C++ : réorganiser la chaîne donnée pour former une chaîne répétée K

Étant donné une chaîne et un entier k, nous devons réorganiser les caractères de la chaîne afin qu'elle devienne une concaténation de k sous-chaînes similaires. Si cela n'est pas possible, le résultat est "Impossible".

string = "malaalam";
K = 2;
res = solve(s, K);

Exemple (en utilisant une carte)

Prenons une chaîne "mottom" et K=2. Une chaîne donnée peut être représentée comme une concaténation de 2 sous-chaînes comme tomtom, motmot omtomt, etc. Comme pour les 3 sous-chaînes, lorsque k = 2, les deux sous-chaînes sont concaténées.

À l'aide de chaînes, nous pouvons déterminer le nombre d'occurrences de chaque caractère. Après cela, si toutes les fréquences disponibles sont divisibles par k, alors c'est possible et nous pouvons produire n'importe quelle réponse possible. Sinon c'est impossible.

L'implémentation C++ de l'exemple ci-dessus est la suivante -

#include <iostream>
#include <map>
using namespace std;
string solve(string s, int k) {
   map<char, int> mp;
   for (char ch : s) {
      mp[ch]++;
   }
   string repeatedSubstring = "";
   for (auto &val : mp) {
      if ((val.second % k) != 0) {
         return "Impossible";
      }
      else {
         for (int i=0;i<val.second/k;i++) {
            repeatedSubstring+=val.first;
         }
      }
}
string ans = "";
for (int i = 0; i < k; i++) {
   ans+= repeatedSubstring;
}
return ans;
}
int main() {
   string s = "mottom";
   int K = 2;
   cout << solve(s, K);
   return 0;
}

Sortie

motmot

Exemple (sans carte)

Une implémentation C++ du même exemple (sans utiliser de mappage) est la suivante -

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

int main() {
    string str = "mottom";
    int k = 2;
    int frqncy[26] = { 0 };

    int len = str.length();

    for (int i = 0; i < len; i++) {
        frqncy[str[i] - 'a']++;
    }
    string single_copy = "";
    for (int i = 0; i < 26; i++) {
        if (frqncy[i] != 0) {

            if ((frqncy[i] % k) != 0) {

                string ans = "Not Possible";
                cout << ans;
            } else {

                int total_occurrences = (frqncy[i] / k);

                for (int j = 0; j < total_occurrences; j++) {
                    single_copy += char(i + 97);
                }
            }
        }
    }
    string kString;
    for (int i = 0; i < k; i++) {
        kString += single_copy;
    }
    cout << kString;
    return 0;
}

Sortie

motmot

Conclusion

Nous pouvons utiliser map ou unordered_map pour hacher les caractères en fréquences. Nous pouvons utiliser un tableau [26] pour représenter les caractères latins minuscules et définir toutes les fréquences sur 0. Il s'agit d'une question basée sur l'implémentation et a une complexité temporelle de O(n), en utilisant unordered_map ou hashmap.

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!