C++程序：将给定字符串重新排序以形成K个连接的字符串

给定一个字符串和一个整数 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

结论

我们可以使用 map 或 unordered_map 将字符映射到频率。我们可以使用 [26] 的数组表示拉丁小写字符，并将所有 freq 设置为 0。这是一个基于实现的问题，使用 unordered_map 或 hashmap 的时间复杂度为 O(n)。

更新于: 2022年8月10日

102 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告