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

結論

我們可以使用映射或 unordered_map 將字元哈希到頻率。我們可以使用 [26] 數組來表示拉丁小寫字符，並將所有頻率設為 0。這是一個基於實作的問題，時間複雜度為 O(n)，使用 unordered_map 或 hashmap。

以上是C++程式：重新排列給定的字串以形成一個K重複的字串的詳細內容。更多資訊請關注PHP中文網其他相關文章！