给定一个字符串和一个整数k，我们需要对字符串中的字符重新排序，使其成为k个相似子串的串联。如果不可能，则输出结果为“Impossible”。
string = "malaalam"; K = 2; res = solve(s, K);
让我们有一个字符串“mottom”并且 K=2。给定的字符串可以表示为 2 个子字符串的串联，如 tomtom、motmot omtomt 等。与所有 3 个子字符串一样，当 k = 2 时，两个子字符串连接在一起。
使用字符串，我们可以确定每个字符出现的次数。之后，如果所有可用的频率都能被k整除，那么就有可能，我们可以输出任何可能的答案。否则不可能。
上述示例的C++实现如下 -
#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
同一示例的 C++ 实现（不使用映射）如下 -
#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
我们可以使用映射或 unordered_map 将字符哈希到频率。我们可以使用 [26] 数组来表示拉丁小写字符，并将所有频率设置为 0。这是一个基于实现的问题，时间复杂度为 O(n)，使用 unordered_map 或 hashmap。
以上是C++程序：重新排列给定的字符串以形成一个K重复的字符串的详细内容。更多信息请关注PHP中文网其他相关文章！
