# HackerEarth Two types of queries problem solution

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.

`#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 18using 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 functionll 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();            }        }    }}`