PROBLEM LINK:
Setter: Jeevan Jyot Singh
Tester: Aryan Chaudhary
Editorialist: Rishabh Gupta
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
A string A of length N is said to be anti-palindrome, if for each 1≤i≤N , A_i≠A_{(N+1−i)}.
You are given a string A of length N (consisting of lowercase Latin letters only). Rearrange the string to convert it into an anti-palindrome or determine that there is no rearrangement which is an anti-palindrome.
If there are multiple rearrangements of the string which are anti-palindromic, print any of them.
QUICK EXPLANATION
What is the condition for NO answer?
If the string is of odd length the answer must be NO, because of the centremost letter. Otherwise, intuitively we can observe that if a letter occurs more than n/2 times there can not be any rearrangement possible. Can be also proved by pigeonhole priciple.
How to rearrange if no letter appears > n/2 times in an even length string?
We can sort the string. Now we reverse the right half of the string, that way letters at a[i] and a[i +n/2] are against each other. Since no letter appears > n/2 times both these characters are different.
EXPLANATION:
For a string with odd length the answer is always NO because of the centremost character. So, from now on we’ll deal with the even length strings.
If any character appears more than n/2 times, using pigeonhole principle we can conclude that no arrangement is possible. If it is not the case, we can make a arrangement by sorting the string and putting the a[i] and a[i + n/2 ] characters against each other. So, our rearrranged string will look like a[1], a[2], … a[n/2], a[n], a[n-1] … a[n/2 + 1].
TIME COMPLEXITY:
O(n) for each test case.
SOLUTION:
Setter's Solution
#ifdef WTSH
#include <wtsh.h>
#else
#include <bits/stdc++.h>
using namespace std;
#define dbg(...)
#endif
#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;
const long long INF = 1e18;
const int N = 1e6 + 5;
void solve()
{
int n; cin >> n;
string s; cin >> s;
array<int, 26> cnt{};
for(char c: s)
cnt[c - 'a']++;
if(n % 2 == 1 or *max_element(cnt.begin(), cnt.end()) > n / 2)
cout << "NO\n";
else
{
cout << "YES\n";
sort(s.begin(), s.end());
reverse(s.begin() + n / 2, s.end());
cout << s << endl;
}
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T; cin >> T;
for(int tc = 1; tc <= T; tc++)
{
// cout << "Case #" << tc << ": ";
solve();
}
return 0;
}
Editorialist''s Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define dd double
#define endl "\n"
#define pb push_back
#define all(v) v.begin(),v.end()
#define mp make_pair
#define fi first
#define se second
#define vll vector<ll>
#define pll pair<ll,ll>
#define fo(i,n) for(int i=0;i<n;i++)
#define fo1(i,n) for(int i=1;i<=n;i++)
ll mod=1000000007;
ll n,k,t,m,q,flag=0;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(a) -- no. of elements strictly less than a
// s.find_by_order(i) -- itertor to ith element (0 indexed)
ll min(ll a,ll b){if(a>b)return b;else return a;}
ll max(ll a,ll b){if(a>b)return a;else return b;}
ll gcd(ll a , ll b){ if(b > a) return gcd(b , a) ; if(b == 0) return a ; return gcd(b , a%b) ;}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifdef NOOBxCODER
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
#define NOOBxCODER 0
#endif
cin>>t;
//t=1;
while(t--){
cin>>n;
string s;
cin>>s;
if(n%2==1){cout<<"NO"<<endl; continue;}
sort(all(s));
string ans; fo(i,n)ans.pb('0');
int flag=0;
fo(i, n/2){
if(s[i] == s[i + n/2])flag=1;
ans[i]=s[i];
}
for(int i= n/2 ; i<n;i++){
ans[i] = s[n-1 + n/2 - i];
}
if(flag){cout<<"NO"<<endl; continue;}cout<<"YES"<<endl;
cout<<ans<<endl;
}
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
return 0;
}
