Link to the problem : Cf_739_E I am getting TLE in test case — 5 and have gone through the code many times, but cannot find any bug or optimisation. Any help is appreciated.
ll solve()
{
string s;
cin >> s;
vector<ll> st(26, 0);
string rm = "";
string final = "";
for (ll i = s.size() — 1; i >= 0; i--)
{
if (st[s[i] — 'a'] == 0)
{
st[s[i] — 'a'] = 1;
rm = rm + s[i];
}
else
{
st[s[i] — 'a']++;
}
}
reverse(rm.begin(), rm.end());
ll total = 0;
for (ll i = 0; i < rm.size(); i++)
{
if (st[rm[i] — 'a'] % (i + 1) != 0)
{
cout << -1 << endl;
return 0;
}
st[rm[i] — 'a'] = st[rm[i] — 'a'] / (i + 1);
total += st[rm[i] — 'a'];
}
vector<ll> st2(26, 0);
for (ll i = 0; i < total; i++)
{
final = final + s[i];
st2[s[i] — 'a']++;
}
ll start = total;
string tmp = final;
string sb = final;
for (ll i = 0; i < rm.size(); i++)
{
string tmp2 = "";
for (ll j = 0; j < tmp.size(); j++)
{
if (tmp[j] != rm[i])
{
tmp2 += tmp[j];
}
}
tmp = tmp2;
sb += tmp2;
}
if (sb != s)
{
cout << -1 << endl;
return 0;
}
cout << final << " " << rm << endl;
return 0;
}