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);
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;
}
motmot
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;
}
motmot
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!
