C++ Program: Rearrange the given string to form a K repeated string

Given a string and an integer k, we need to reorder the characters in the string so that it becomes a concatenation of k similar substrings. If this is not possible, the output is "Impossible".

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

Example (using map)

Let us have a string "mottom" and K=2. A given string can be represented as a concatenation of 2 substrings like tomtom, motmot omtomt, etc. As with all 3 substrings, when k = 2, the two substrings are concatenated.

Using strings, we can determine the number of occurrences of each character. After that, if all available frequencies are divisible by k, then it is possible, and we can output any possible answer. Otherwise it's impossible.

The C implementation of the above example is as follows -

#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

Example (without map)

A C implementation of the same example (without mapping) is as follows -

#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

in conclusion

We can use map or unordered_map to hash characters to frequencies. We can use a [26] array to represent Latin lowercase characters and set all frequencies to 0. This is an implementation-based question and has a time complexity of O(n), using unordered_map or hashmap.

The above is the detailed content of C++ Program: Rearrange the given string to form a K repeated string. For more information, please follow other related articles on the PHP Chinese website!