HackerEarth Shil and Lucky String problem solution

In this HackerEarth Shil and Lucky String problem solution Shil is your new boss and he likes lucky strings very much. A string is called lucky if and only if each character from first half of the string can be paired to each character from second half of the string. AND:

In each pair, a character from the first half is strictly greater than a character from the second half OR

In each pair, a character from the first half is strictly lesser than a character from the second half OR

In each pair, a character from the first half is equal to character from the second half.

Each character should be used exactly once in pairing.

Your are given a string S. You want to change the minimum number of characters to make this string lucky so that you can gift it to your boss.

Note that each character in lucky string should be in lower case alphabet ( 'a' - 'z' ).

HackerEarth Shil and Lucky String problem solution.

#include<bits/stdc++.h>
using namespace std;
#define INF 10000000000000000
#define f first
#define pii pair<pi,ll>
#define pi pair<ll,ll>
#define pb push_back

#define ll long long
#define s second
#define rep(i,n) for(int i=0;i<n;i++)
#define mp make_pair
#define fr freopen("input-3.txt","r",stdin)
#define fo freopen("output-3.txt","w",stdout)
#define mod 1000000007
int calc_equal(string a,string b){
   int f[26]={0};
   for(auto x:a){
      f[x-'a']++;
   }
   int ans=0;
   for(auto x:b){
      if(f[x-'a']>0){
         f[x-'a']--;
      }
      else{
         ans++;
      }
   }
   return ans;
}
int calc(string a,string b){
   int cnt=0;
   for(int i=0;i<a.size();i++){
      if(a[i]=='z') a[i]='a' , cnt++;
      if(b[i]=='a') b[i]='z' , cnt++;
   }
   int ans=0;
   int f[26]={0};
   for(auto x:b){
      f[x-'a']++;
   }
   sort(a.begin(),a.end());
   sort(b.begin(),b.end());
   bool go;
   for(auto x:a){
      go=1;
      for(int j=int(x-'a')+1;j<26;j++){
         if(f[j]>0){
            f[j]--;
            go=0;
            break;
         }
      }
      if(go) ans++;
   }
   ans+=cnt;
   return ans;
}
int main(){

   int N;
   cin >> N;
   string s;
   cin >> s;
   string a,b;
   a=s.substr(0,N/2);
   b=s.substr(N/2,N/2);

   string ap=a , bp =b;
    int ans=calc_equal(ap,bp);
   sort(a.begin(),a.end());
   sort(b.begin(),b.end());
// cout<<a<<" "<<b<<"\n";
   ans=min(ans,calc(a,b));
   ans=min(ans,calc(b,a));
   //cout<<calc(b,a);
   cout<<ans;
}

Second solution

#include <iostream>
#include <cstdio>
#include <string>
#include <sstream> 
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <cassert>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define SZ(x) ((int)(x.size()))
#define fi first
#define se second
#define FOR(i,n) for(int (i)=0;(i)<(n);++(i))
#define FORI(i,n) for(int (i)=1;(i)<=(n);++(i))
#define IN(x,y) ((y).find((x))!=(y).end())
#define ALL(t) t.begin(),t.end()
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
#define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
#define REMAX(a,b) (a)=max((a),(b));
#define REMIN(a,b) (a)=min((a),(b));
#define DBG cerr << "debug here" << endl;
#define DBGV(vari) cerr << #vari<< " = "<< (vari) <<endl;

typedef long long ll;
const int N = 100000;
int cnt[2][26];
int cti(char c) { return (int) (c - 'a'); }
int main()
{
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    assert(n >= 1); assert(n <= N); assert(n % 2 == 0);
    string s;
    cin >> s;
    assert(s.length() == n);
    FOR(i, n) 
    {
        assert(s[i] >= 'a');
        assert(s[i] <= 'z');
    }
    //cout << s << endl;
    int res[3] = {0, 0, 0};
    //res0 //greater letters in first half
    int good = 0;
    int i = 0, j = n / 2;
    string w = s;
    int extra_cost = 0;
    FOR(i, n / 2)
    {
        if(w[i] == 'a')
        {
            ++extra_cost;
            w[i] = 'z';
        }
    }
    REP(i, n / 2, n - 1)
    {
        if(w[i] == 'z')
        {
            ++extra_cost;
            w[i] = 'a';
        }
    }
    sort(w.begin(), w.begin() + n / 2);
    sort(w.begin() + n / 2, w.end());
    while(i < n / 2 && j < n)
    {
        if(w[i] > w[j])
        {
            ++good;
            ++i;
            ++j;
        }
        else
        {
            ++i;
        }
    }
    res[0] = (n - 2 * good) / 2 + extra_cost;
    //res1 //smaller letters in first half
    good = 0;
    i = 0;
    j = n / 2;
    extra_cost = 0;
    w = s;
    FOR(i, n / 2)
    {
        if(w[i] == 'z')
        {
            ++extra_cost;
            w[i] = 'a';
        }
    }
    REP(i, n / 2, n - 1)
    {
        if(w[i] == 'a')
        {
            ++extra_cost;
            w[i] = 'z';
        }
    }
    sort(w.begin(), w.begin() + n / 2);
    sort(w.begin() + n / 2, w.end());
    while(i < n / 2 && j < n)
    {
        if(w[i] < w[j])
        {
            ++good;
            ++i;
            ++j;
        }
        else
        {
            ++j;
        }
    }
    res[1] = (n - 2 * good) / 2 + extra_cost;
    //res2 //equal letters
    FOR(i, n / 2) cnt[0][cti(s[i])]++;
    REP(i, n / 2, n - 1) cnt[1][cti(s[i])]++;
    res[2] = 0;
    FOR(i, 26) res[2] += max(cnt[0][i], cnt[1][i]) - min(cnt[0][i], cnt[1][i]);
    res[2] /= 2;
    
    //cout << res[0] << " " << res[1] << " " << res[2] << endl;
    cout << min(res[0], min(res[1], res[2])) << endl;
    return 0;
}