ANTI_PAL Editorial

PROBLEM LINK:

https://www.codechef.com/START24C/problems/ANTI_PAL

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;
}

3 Likes

Can anyone tell why this fails?
https://www.codechef.com/viewsolution/57603137

2 Likes

This was my code :
public static void main (String[] args) throws java.lang.Exception {
Scanner s = new Scanner(System.in);
int testCases = s.nextInt();
while (testCases-- != 0) {
int strLen = s.nextInt();
String str = s.next();

        if (strLen % 2 != 0) { // if string length = odd, then the middle element will always be palindrome
            System.out.println("NO");
            continue;
        }

        Map<Character, Integer> map = new HashMap<>(26); // keeps counts of each alphabet
        boolean flag = true;
        for (int i = 0; i < str.length(); i++)
        {
            map.put(str.charAt(i), map.getOrDefault(str.charAt(i), 0) + 1);
            if (map.get(str.charAt(i)) > str.length()/2) {
                flag = false;
                break;
            }
        }
        if (!flag) {
            System.out.println("NO");
            continue;
        }

        Object[] a = map.entrySet().toArray(); //sort the array based on number of occurences of each element
        Arrays.sort(a, new Comparator() {
            public int compare(Object o1, Object o2) {
                return ((Map.Entry<Character, Integer>) o2).getValue()
                        .compareTo(((Map.Entry<Character, Integer>) o1).getValue());
            }
        });

        System.out.println("YES");
        for (Object e : a) {
            int temp = ((Map.Entry<Character, Integer>) e).getValue();
            for (int i = 0; i < temp; i++)
            {
                System.out.print(((Map.Entry<Character, Integer>) e).getKey());
            }
        }
        System.out.println("");
    }
}

My approach here was to add all the characters in a hashMap and then sort the map by the number of times the character was occurring. Then I would output the string in a way that the letter occurring the highest times was printed first , the second highest occurrence letter was printed second and so on

My code passed all the testcases but failed in all but 1 testcase while submitting. Can someone tell me what am I doing wrong?

My code fails two test cases, can someone help so that i can sleep peacefully tonight XD
https://www.codechef.com/viewsolution/57646024

If we are sorting the string shouldn’t it be O(N log N) ?

it will take NlogN but it will not give TLE in this case

1 Like

Consider the TC: aaaaccbbbb (a* 4 , b* 4, c* 2)
Your Output: aaaabbbbcc (which is pallindrome at position 5)
Actual Output: aaaabcbcbb

1 Like

I think you can use something like counting sort as we have only 26 characters that will work in O(n)

I’ve tried similar approach and mine was failing test cases 1,2

1 Like

Did you find any test case which was failing against your approach which was similar to me?

Still finding…will update when I do

1 Like

I got AC using using the same approach. I did a stupid silly mistake in initializing a variable named “howmuch”. It should be int instead of char.

See line 23 in my WA submission.
See line 24 in my AC submission.

My bad!

1 Like

I got AC as well
Solution: 57652352 | CodeChef :smiley:

1 Like

1
8
aaabbbcc

can someone please tell me why my code is failing i have tried a lot to find but not getting it

#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
#define ll long long
#define fl(i,n) for(int i=0;i<n;i++)
#define vr(v) v.begin(),v.end()

signed main()
{
fast;
int tc;
cin>>tc;
while(tc–)
{
int n;
cin>>n;
string s;
cin>>s;
if(n&1){
cout<<“NO\n”;
continue;
}

    vector<pair<int,char>>v(26);
    for (int i = 0; i < s.length(); i++)
    {
        v[s[i]-'a'].first++;
        v[s[i]-'a'].second=s[i];
    }
   sort(v.begin(),v.end());
   int maxi=v[v.size()-1].first;
    if(maxi>n/2){
        cout<<"NO\n";
        continue;
    }

    string ans="";
   for (int i = v.size()-1; i >=0; i--)
   {
       char k=v[i].second;
       for (int j = 0; j < v[i].first; j++)
       {
           ans+=k;
       }
       
   }
   int kk=ans.length();
    if(ans[kk/2]==ans[kk/2-1]){
        swap(ans[kk/2],ans[0]);
    }
    cout<<"YES\n";
    cout<<ans<<"\n";
    
}

return 0;
}

CAN ANYONE TELL ME MY MISTAKE???PLS

#include<bits/stdc++.h>
using namespace std;
int main(){
int T;
cin>>T;
while(T–){
int n; unordered_map<char,int>m; int count=0;
cin>>n;
string s;
cin>>s;
if(n%2!=0)
cout<<“NO”<<endl;
else{
for(int i=0;i<n;i++){
m[s[i]]++;
}
for(auto it:m){
if(it.second>n/2)
{
cout<<“NO”<<endl;
count=1;
break;
}
}
if(count==0){
sort(s.begin(),s.end());
for(int i=(n/2)-1;i>=0;i–){
if(s[i]==s[n-i-1])
swap(s[n-i],s[n/2+i]);
}
cout<<“YES”<<endl;
cout<<s<<endl;
}

}
}
return 0;
}

check for basic tests like if the string size if odd return no; and other cases like aaaabbbbbb
aaaa
aaabbbccc

My approach was to sort the string first.
Then check for the condition of anti palindrome
if it is not satisfied I just swap that character with the first unswapped character.
and then after I do this operation for the entire string.
I just check now if the string has become anti-palindrome.
if it is not just print NO.

My solution: Here

1 Like

Thank you so much bro.

1 Like

My approach was to sort the string first ,
Then reverse the first half of the string
and then check for anti palindrome .

My solution : ANTI_PAL

1 Like