HackerEarth Two types of queries problem solution

by
In this HackerEarth Two types of queries problem solution you are given a string str. It costs one unit of a coin to change a character at an index. Your task is to convert it into a palindrome with minimum coins. Also, you are given  number of queries. The queries are of the following types:
  • 1 A B
  • 2
After solving the first type of query, you can convert character A into character B without any cost and vice versa. In the second type of query, you are required to answer the minimum cost that is required to convert the given string into a palindrome.
HackerEarth Two types of queries problem solution

HackerEarth Two types of queries problem solution.

#include <bits/stdc++.h>
#define ll long long
#define int ll
#define mod 1000000007
#define mod2 998244353
#define MAXN 200000 + 5
#define MAXM 100000 + 5
#define MAXV 1000000 + 5
#define LOGN 18
using namespace std;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(arr) arr.begin() , arr.end()
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define rep(i , a , n) for(ll i = a ; i < n ; i++)
#define s(arr) sort(all(arr))
#define r(arr) reverse(all(arr))
#define rs(arr) s(arr) ; r(arr)
#define con continue

//debug
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define trace7(a, b, c, d, e, f , g) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<< f << " | "<< #g <<": "<<g<<endl
#define trace8(a, b, c, d, e, f , g , h) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<< f << " | " << #g <<": "<< g <<" | "<<#h<< ": " << h << endl

// mod helpers function
ll sum_mod(ll a , ll b , ll m = mod2){
    return (a + b) % m;
}

ll minus_mod(ll a , ll b , ll m = mod2){
    return ((a - b) % m + m) % m;
}

ll mul_mod(ll a , ll b , ll m = mod2){
    return (a * b) % m;
}

ll modexpo(ll a , ll b){
    ll res = 1;
    while(b){
        if (b % 2 == 1)
            res = mul_mod(res , a);
        a = mul_mod(a , a);
        b /= 2;
    }
    return res;
}

struct DSU{
    int size;
    vector<int> id;
    vector<int> si;
    vector< vector < int > > adj;
    DSU(int x)
    {
        size = x;
        id.resize(x + 1);
        si.resize(x + 1);
        for (int i = 1 ; i <= x ; i++)
        {
            id[i] = i , si[i] = 1;
        }
    }
    
    int getRoot(int a)
    {
        while(a != id[a])
            a = id[a];
        return a;
    }
    void merge(int a , int b)
    {
        if (si[a] < si[b])
        {
            swap(a , b);
        }
        si[a] += si[b];
        id[b] = id[a];
    }
    
    void fun(int a , int b)
    {
        int x = getRoot(a);
        int y = getRoot(b);
        if (x == y)
            return;
        merge(x , y);
    }
};

void solve() {
    int n;
    cin >> n;
    string str;
    cin >> str;
    struct DSU temp(26);
    int q;
    cin >> q;
    int prevans = 0;
    map < pair < int , int > , int > ma;
    for (int i = 0 ; i < n / 2 ; i++){
        if (str[i] != str[n - 1 - i]){
            prevans++;
            int val1 = str[i] - 'a';
            int val2 = str[n - 1 - i] - 'a';
            if (val1 > val2)
                swap(val1 , val2);
            ma[mp(temp.getRoot(val1) , temp.getRoot(val2))]++;
        }
    }
    while(q--){
        int type;
        cin >> type;
        if (type == 1){
            char a , b;
            cin >> a >> b;
            int val1 = a - 'a';
            int val2 = b - 'a';
            if (temp.getRoot(val1) == temp.getRoot(val2))
                con;
            temp.fun(a - 'a' , b - 'a');
            map < pair < int , int > , int > ma1;
            for (auto it : ma) {
                int val1 = it.ff.ff;
                int val2 = it.ff.ss;
                int val1Root = temp.getRoot(val1);
                int val2Root = temp.getRoot(val2);
                if (val1Root == val2Root)
                    prevans -= it.ss;
                else {
                    if (val1Root > val2Root)
                        swap(val1Root , val2Root);
                    ma1[{val1Root , val2Root}]+= it.ss;
                }
            }
            ma = ma1;
        }
        else {
            cout << prevans << endl;
        }
    }
}

signed main(){
    FAST;
    int t = 1;
    while(t--){
        solve();
    }
    return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 2e5 + 14, z = 26;
bool ok[z][z];
int n, q;
string s;
int get(){
    int ans = 0;
    for(int i = 0; i < n / 2; i++)
        ans += !ok[s[i] - 'a'][s[n - i - 1] - 'a'];
    return ans;
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    for(int i = 0; i < z; i++)
        ok[i][i] = 1;
    cin >> n >> s >> q;
    int ans = get();
    while(q--){
        int t;
        cin >> t;
        if(t == 2)
            cout << ans << 'n';
        else{
            char a, b;
            cin >> a >> b;
            a -= 'a', b -= 'a';
            if(!ok[a][b]){
                for(int i = 0; i < z; i++)
                    for(int j = 0; j < z; j++)
                        ok[i][j] |= ok[i][a] && ok[b][j] || ok[i][b] && ok[a][j];
                ans = get();
            }
        }
    }
}