C++ 程序重新排序给定的字符串以形成 K 连接字符串
c++programmingserver side programming
给定一个字符串和一个整数 k，我们需要重新排序字符串中的字符，使其成为 k 个相似子字符串的连接。如果不可能，则将结果输出为"不可能"。
string = "malaalam"; K = 2; res =solve(s, K);
示例(使用 Maps)
假设有一个字符串"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
结论
我们可以使用 map 或 unordered_map 将字符哈希化为频率。我们可以使用 [26] 数组来存储拉丁小写字符，并将所有频率设置为 0。这是一个基于实现的问题，使用 unordered_map 或 hashmap 时，时间复杂度为 O(n)。
