Repeating Strings

Time Limit: 1000ms

Memory Limit: 256MB

Repeating Strings

Submissions Submit

There are $3$ main types of repeating strings:
A string is of type $1$ if the string can be rearranged such that it becomes in the form $aaa...a$ where $a$ is a string and is repeated $k$ times. For example, if k is 2, "craarc" can be rearranged to become "carcar", which is the string "car" repeated twice.
A string is of type $2$ if it's not of type $1$ and it can be rearranged to become in the form of $a...ap$ where $p$ is a prefix of $a$, and $a$ is repeated $k$ times. For example, if k is 2, "acraarcc" can be rearranged to become "carcarca", where a is "car" and p is "ca", which is a prefix of "car".
A string is of type $3$ otherwise.
Given a string $s$ of length $n$, and $k$ which is the number of times $a$ repeats. Print the type of the string and the string after rearrangement if it's not of the 3rd type.

Input

The first line of input contains two integers $n$ and $k$ $(1 \leq k \leq n \leq 10^6)$.
The second line contains a single string $s$, consisting of $n$ lowercase letters.

Output

Print the type of the string on the first line. If the string is not of the $3^{rd}$ type, then print the rearranged string on the second line.
If there are multiple solutions, print any.

Samples

Input	Output
12 3 aaccbbabcddd Copy	1 abcdabcdabcd Copy
10 2 zigzagiaai Copy	2 aigzaigzai Copy
7 4 fegtyta Copy	3 Copy

Find the frequency of each letter in $s$.

The string is of type $1$ if $freq_i$ $(mod)$ $k = 0$.
The string is of type $2$ if $freq_i$ $(mod)$ $k \leq \frac{freq_i}{k}$
Otherwise, the string is of type $3$.

If the string is of the $1^{st}$ type, then create a string with $\frac{freq_i}{k}$ copies of each character $i$, then repeat it until the length equals $n$.

If the string is of the second type then fill a string with $freq_i$ $(mod)$ $k$ copies of each character $i$, then add $\frac{freq_i}{k}$ $-$ $freq_i$ $(mod)$ $k$ copies of each character $i$, then repeat the string until the length is more than $n$, then remove the last character until the length becomes equal to $n$.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

string s,ans,temp;
int freq[26],n,k;
bool type;

int main(){
    cin >> n >> k >> s;
    for(auto i : s)freq[i - 'a']++;
    for(int i = 0;i < 26;i++){
        int ok = freq[i]%k;
        if(ok > freq[i]/k)return puts("3"),0;
        type|=freq[i]%k;
        while(ok--)temp+=i + 'a';
    }
    for(int i = 0;i < 26;i++){
        int ok = freq[i]/k - freq[i]%k;
        while(ok--)temp+=i + 'a';
    }
    printf("%d\n",(int)type + 1);
    while(ans.size() < n)ans+=temp;
    while(ans.size() > n)ans.pop_back();
    puts(ans.c_str());
}