Sort Them

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

#define rev_string(s) reverse(s.begin(),s.end());

#define srt_d(arr,n) sort(arr,arr+n,greater<int>())
#define srt_v(vec) sort(vec.begin(),vec.end())
#define srt_v_d(vec) sort(vec.begin(),vec.end(),greater<int>())
#define srt_v_a_sec(vec) sort(vec.begin(),vec.end(),[](const pair<int,int>& a,const pair<int,int>& b){return a.second<b.second;})

typedef long long ll;

int main()
{
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        string s,p;
        cin>>s>>p;
        map<char,char> mpp;
        
//map all the character at index i to its compliment in string p

        for(int i=0;i<26;i++){
            mpp[p[i]]=p[25-i];
        }
        
//initialise 2D vector dp with n rows 2 columns which are initialised with 1e6 as per question constraint, I took 1e6 to be on the safe side beacause 1e6 >= n(3e5)

        vector<vector<int>> dp(n, vector<int>(2,1e6));
        
 
        dp[0][0]=0;
        dp[0][1]=1;


        for(int i=1;i<n;i++){
            int first_p=1e6,second_p=1e6,third_p=1e6,fourth_p=1e6;
            
            if(s[i]>=s[i-1]){
                first_p=dp[i-1][0];
            }
            
            if(s[i]>=mpp[s[i-1]]){
                second_p=dp[i-1][1];
            }
            
            if(mpp[s[i]]>=s[i-1]){
                third_p=1+dp[i-1][0];
            }
            
            if(mpp[s[i]]>=mpp[s[i-1]]){
                fourth_p=1+dp[i-1][1];
            }
            
            dp[i][0]=min(first_p,second_p);
            dp[i][1]=min(third_p,fourth_p);
        }
        


        int ans=min(dp[n-1][0],dp[n-1][1]);
        if(ans==1e6) cout<<-1<<endl;
        else cout<<ans<<endl;
    }
    return 0;
}