Program C++: Susun semula rentetan yang diberikan untuk membentuk rentetan berulang K

Diberi rentetan dan integer k, kita perlu menyusun semula aksara dalam rentetan supaya ia menjadi gabungan k subrentetan yang serupa. Jika ini tidak mungkin, outputnya adalah "Mustahil".

string = "malaalam";
K = 2;
res = solve(s, K);

Contoh (menggunakan peta)

Mari kita mempunyai rentetan "mottom" dan K=2. Rentetan yang diberikan boleh diwakili sebagai gabungan 2 subrentetan seperti tomtom, motmot omtomt, dsb. Seperti semua 3 subrentetan, apabila k = 2, dua subrentetan itu digabungkan.

Menggunakan rentetan, kita boleh menentukan bilangan kejadian setiap aksara. Selepas itu, jika semua frekuensi yang tersedia boleh dibahagikan dengan k, maka ia adalah mungkin, dan kita boleh mengeluarkan sebarang jawapan yang mungkin. Jika tidak mustahil.

Implementasi C++ bagi contoh di atas adalah seperti berikut -

#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;
}

Output

motmot

Contoh (tanpa peta)

Perlaksanaan C++ contoh yang sama (tanpa menggunakan pemetaan) adalah seperti berikut -

#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;
}

Output

motmot

Kesimpulan

Kami boleh menggunakan peta atau unordered_map untuk mencincang aksara kepada frekuensi. Kita boleh menggunakan tatasusunan [26] untuk mewakili aksara huruf kecil Latin dan menetapkan semua frekuensi kepada 0. Ini ialah soalan berasaskan pelaksanaan dan mempunyai kerumitan masa O(n), menggunakan unordered_map atau hashmap.

Atas ialah kandungan terperinci Program C++: Susun semula rentetan yang diberikan untuk membentuk rentetan berulang K. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!