Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
The only bad substrings both end with T: FFT and NTT. So the danger is not “having these letters”, it is putting T after the wrong letters.
To create FFT, some T must appear immediately after two consecutive Fs. To create NTT, two consecutive Ts must appear immediately after an N.
A very heavy-handed way to avoid both is to make sure every T appears before every F and every N. Then neither bad substring can even start correctly and end with T.
Sorting the whole string in reverse alphabetical order does exactly that: T comes before N, and N comes before F.
So the entire constructive algorithm can be: for each string, sort its characters in decreasing order and print it. This is one of those 800s where the hammer is genuinely the right tool.
The statement asks us to rearrange the letters of so that the final string does not contain either bad contiguous substring:
FFTNTTWe do not need to keep the string close to the original. We can output any permutation that works.
Key Observation
Both forbidden strings require a T to appear after another important letter:
FFT needs two Fs followed by a T.NTT needs an N followed by two Ts.So if we arrange the string so that every T comes before every F and every N, then both patterns become impossible.
Why?
FFT, the final character is T. But if all Ts are before all Fs, then no T can appear after two Fs.NTT, the last two characters are T T. But if all Ts are before all Ns, then no N can appear before those Ts in that order.That kills both forbidden substrings instantly. No fancy DP, no graph theory, no heroic nonsense.
How to Construct It
Sort the string in decreasing alphabetical order.
Since uppercase letters are ordered alphabetically, reverse sorting puts letters like this around the important ones:
So every T is placed before every N and every F.
That means:
FFT cannot happen, because T never comes after F.NTT cannot happen, because T never comes after N.Other letters do not matter. They can sit wherever the sort puts them.
Correctness Proof
Let be the string obtained by sorting in decreasing alphabetical order.
First, is a rearrangement of , because sorting only changes the order of characters and does not add or remove anything.
Now consider the forbidden substring FFT. If FFT appeared in , then some T would appear after an F. But in decreasing alphabetical order, T is alphabetically greater than F, so every T appears before every F. Contradiction. Therefore FFT cannot appear.
Next consider the forbidden substring NTT. If NTT appeared in , then some T would appear after an N. But T is alphabetically greater than N, so every T appears before every N. Contradiction. Therefore NTT cannot appear.
Since neither forbidden substring appears, is not difficult. Thus the algorithm is correct.
Complexity
For a string of length , sorting takes time. Across all test cases, the total length is at most , so this easily fits.
The memory usage is extra apart from the string storage, ignoring the sort implementation details.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
sort(s.rbegin(), s.rend());
cout << s << '\n';
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
sort(s.rbegin(), s.rend());
cout << s << '\n';
}
return 0;
}