C++-Programm: Ordnen Sie die angegebene Zeichenfolge neu an, um eine K wiederholte Zeichenfolge zu bilden

Bei einer gegebenen Zeichenfolge und einer Ganzzahl k müssen wir die Zeichen in der Zeichenfolge neu anordnen, damit sie zu einer Verkettung von k ähnlichen Teilzeichenfolgen wird. Ist dies nicht möglich, erfolgt die Ausgabe „Impossible“.

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

Beispiel (mit Karte)

Lassen Sie uns eine Zeichenfolge „Motto“ und K=2 haben. Eine bestimmte Zeichenfolge kann als Verkettung von zwei Teilzeichenfolgen wie tomtom, motmot omtomt usw. dargestellt werden. Wie bei allen drei Teilzeichenfolgen werden die beiden Teilzeichenfolgen verkettet, wenn k = 2.

Mithilfe von Zeichenfolgen können wir die Häufigkeit des Vorkommens jedes Zeichens bestimmen. Wenn danach alle verfügbaren Frequenzen durch k teilbar sind, ist dies möglich und wir können jede mögliche Antwort ausgeben. Sonst ist es unmöglich.

Die C++-Implementierung des obigen Beispiels lautet wie folgt -

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

Ausgabe

motmot

Beispiel (ohne Karte)

Eine C++-Implementierung desselben Beispiels (ohne Verwendung von Mapping) lautet wie folgt -

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

Ausgabe

motmot

Fazit

Wir können „map“ oder „unordered_map“ verwenden, um Zeichen in Häufigkeiten zu hashen. Wir können ein [26]-Array verwenden, um lateinische Kleinbuchstaben darzustellen und alle Häufigkeiten auf 0 zu setzen. Dies ist eine umsetzungsbasierte Frage mit einer Zeitkomplexität von O(n), die unordered_map oder hashmap verwendet.

Das obige ist der detaillierte Inhalt vonC++-Programm: Ordnen Sie die angegebene Zeichenfolge neu an, um eine K wiederholte Zeichenfolge zu bilden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!