# [Solved] Polycarp and String Transformation solution codeforces

## Polycarp and String Transformation solution codeforces

Polycarp has a string ss. Polycarp performs the following actions until the string ss is empty (tt is initially an empty string):

• he adds to the right to the string tt the string ss, i.e. he does t=t+st=t+s, where t+st+s is a concatenation of the strings tt and ss;
• he selects an arbitrary letter of ss and removes from ss all its occurrences (the selected letter must occur in the string ss at the moment of performing this action).

Polycarp performs this sequence of actions strictly in this order.

Note that after Polycarp finishes the actions, the string ss will be empty and the string tt will be equal to some value (that is undefined and depends on the order of removing).

E.g. consider ss=”abacaba” so the actions may be performed as follows:

• tt=”abacaba“, the letter ‘b‘ is selected, then ss=”aacaa“;
• tt=”abacabaaacaa“, the letter ‘a‘ is selected, then ss=”c“;
• tt=”abacabaaacaac“, the letter ‘c‘ is selected, then ss=”” (the empty string).

You need to restore the initial value of the string ss using only the final value of tt and find the order of removing letters from ss.

Input

The first line contains one integer TT (1T1041≤T≤104) — the number of test cases. Then TT test cases follow.

Each test case contains one string tt consisting of lowercase letters of the Latin alphabet. The length of tt doesn’t exceed 51055⋅105. The sum of lengths of all strings tt in the test cases doesn’t exceed 51055⋅105.

Output

For each test case output in a separate line:

• 1−1, if the answer doesn’t exist;
• two strings separated by spaces. The first one must contain a possible initial value of ss. The second one must contain a sequence of letters — it’s in what order one needs to remove letters from ss to make the string tt. E.g. if the string “bac” is outputted, then, first, all occurrences of the letter ‘b‘ were deleted, then all occurrences of ‘a‘, and then, finally, all occurrences of ‘c‘. If there are multiple solutions, print any one.
Example
input

Copy
7
abacabaaacaac
nowyouknowthat
polycarppoycarppoyarppyarppyrpprppp
isi
everywherevrywhrvryhrvrhrvhv
haaha
qweqeewew

output

Copy
abacaba bac
-1
polycarp lcoayrp
is si
everywhere ewyrhv
-1
-1

Note

The first test case is considered in the statement.

# Solution

## Python

for _ in range(int(input())):
t=input()
l=sorted(set(t),key=t.rindex)
c=0
for i in set(t):
if t.count(i)%(l.index(i)+1):
print(-1)
break
c+=t.count(i)//(l.index(i)+1)
else:
s=t[:c]
u=s
for i in l:
s=””.join(j for j in s if j!=i)
u+=s
if u!=t:
print(-1)
else:
print(t[:c],””.join(l))

## Java

import java.io.*;
import java.util.*;

public class CF1560E extends PrintWriter {
CF1560E() { super(System.out); }
Scanner sc = new Scanner(System.in);
public static void main(String[] \$) {
CF1560E o = new CF1560E(); o.main(); o.flush();
}

static final int A = 26;
void main() {
int t = sc.nextInt();
out:
while (t– > 0) {
byte[] cc = sc.next().getBytes();
int n = cc.length;
int[] kk = new int[A];
int cnt = 0;
for (int i = 0; i < n; i++) {
int a = cc[i] – ‘a’;
if (kk[a]++ == 0)
cnt++;
}
byte[] qu = new byte[cnt];
int m = 0;
boolean[] used = new boolean[A];
for (int d = cnt, i = n – 1; i >= 0; i–) {
int a = cc[i] – ‘a’;
if (used[a])
continue;
used[a] = true;
if (kk[a] % d != 0) {
println(-1);
continue out;
}
m += kk[a] /= d;
qu[–d] = cc[i];
}
for (int h = 1, i = 0, j = m; h < cnt; h++) {
int a = qu[h – 1] – ‘a’;
used[a] = false;
for (int j_ = j; i < j_; i++) {
a = cc[i] – ‘a’;
if (!used[a])
continue;
if (cc[i] != cc[j++]) {
println(-1);
continue out;
}
}
}
println(new String(cc, 0, m) + ” ” + new String(qu));
}
}
}

## C++

#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
int t;
cin>>t;
while(t–){
string s,a,r,p;
cin>>s;
reverse(s.begin(),s.end());
vector<int> f(26);
for(char c:s){
if(!f[c-‘a’]) a+=c;
f[c-‘a’]++;
}
reverse(a.begin(),a.end());
int n=0;
for(int i=0;i<a.size();i++)n+=f[a[i]-‘a’]/(i+1);
reverse(s.begin(),s.end());
p=s.substr(0,n);
for(char c : a){
r+=p;
p.erase(remove(p.begin(),p.end(),c),p.end());
}
if(r==s)cout<<s.substr(0,n)<<” “<<a<<endl;
else cout<<“-1″<<endl;
}
}

Also read : Large Square solution codechef

Also read : Bus full of passengers solution codechef

Also read : Friend Groups In A Line solution codechef