Sort Them
Source: codechef
Difficulty: 2071

Sort Them
You are given a string$S$of length$N$that contains only lowercase English letters.
You are also given a string$P$of length$26$, that contains every lowercase English letter exactly once.
You can perform the following operation:
Choose an index$i$($1 \leq i \leq N$).
Let$x = 27 - \text{ord}_P(S_i)$.
Here,$\text{ord}_P(S_i)$denotes the (unique) position of character$S_i$in string$P$.
Then, set$S_i$to$P_x$.
Is it possible to convert$S$into a string that's sorted in non descending order using this operation several times?
If it is possible, also find the minimum number of operations required.
Input Format
The first line of input contains a single integer$T$— the number of test cases.
Each test case consists of three lines of input.
The first line of each test case contains a single integer$N$— the size of the string$S$.
The second line of each test case contains the string$S$, consisting of lowercase English letters.
The third line of each test case contains the string$P$, which contains each lowercase English letter exactly once.
Output Format
For each test case, output on a new line the answer: the minimum number of operations needed to convert$S$into a sorted string, or$-1$if it's impossible to do so.
Constraints$1 \leq T \leq 2\cdot 10^4$$1 \leq N \leq 3\cdot 10^5$$S$and$P$contain only lowercase English letters, i.e, the characters
a, b, c, ..., z
.$P$has length$26$, and$P_i \neq P_j$for$i \neq j$.
The sum of$N$over all test cases does not exceed$3\cdot 10^5$.
Sample 1:
Explanation:
Test case$1$:
Consider the following sequence of operations:
Choose$i = 2$. This does the following:$\text{ord}_P(S_2) = \text{ord}_P(\text{k}) = 15$.$x = 27 - 15 = 12$.
So, we set$S_2$to$P_{12}$, which equals
e
.
The string is now
"aeje"
.
Choose$i = 4$. Following the process, this will set$S_4$to
k
, turning the string into
"aejk"
which is sorted in ascending order.
Test case$2$:
It can be proved that there's no way to sort$S$.

Sample Input:
3
4
akje
xidvzocubhrejqkmfntyglaspw
6
yqobbi
nhxmlarqswzkpgvibejtcyfuod
14
abewamesdwgxzy
njodhifwqrzykpvxmlgtsaubce

Sample Output:
2
-1
6

C++ solution:
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while(T--){
        int N;
        cin >> N;
        string S;
        cin >> S;
        string P;
        cin >> P;
        
        vector<int> pos(26);
        for (int i = 0; i < 26; i++){
            pos[P[i] - 'a'] = i + 1;
        }
        
        vector<char> A(N), B(N);
        for (int i = 0; i < N; i++){
            A[i] = S[i];
            int p = pos[S[i] - 'a'];
            int x = 27 - p;
            B[i] = P[x - 1];
        }
        
        const long long INF = 1LL << 60;
        long long dp0 = 0, dp1 = 1;
        for (int i = 1; i < N; i++){
            long long ndp0 = INF, ndp1 = INF;
            for (int j = 0; j < 2; j++){
                char prev = (j == 0 ? A[i - 1] : B[i - 1]);
                long long cost = (j == 0 ? dp0 : dp1);
                if(cost == INF) continue;
                if(prev <= A[i])
                    ndp0 = min(ndp0, cost);
                if(prev <= B[i])
                    ndp1 = min(ndp1, cost + 1);
            }
            dp0 = ndp0;
            dp1 = ndp1;
        }
        long long ans = min(dp0, dp1);
        cout << (ans >= INF ? -1 : ans) << "\n";
    }
    return 0;
}

Go solution:
package main

import (
    "bufio"
    "fmt"
    "container/list"
    "os"
)

var (
    ck, vst []int64
    lst = list.New()
    skst= []int64{}
    qst = []int64{}
    sst = make(map[int64]bool)
)

const INF int64 = 1e9

func main() {
    r := bufio.NewReader(os.Stdin)
    w := bufio.NewWriter(os.Stdout)
    defer w.Flush()

    var t int
    fmt.Fscan(r, &t)
    
    min:=func (a, b int64) int64 {
    if a >= b {
        return b
    }
    return a
}

    for t > 0 {
        t--

        var n int
        fmt.Fscan(r, &n)
        
        
        nz:=int64(n)
         xq1:= (9 + nz + 40) - nz
 xq2:= (10 + nz + 40) - nz
 fvi:= make([] int64, xq1)
 for i:= range fvi {
     fvi[i] = 89
 }
 fvc:= make([] rune, xq2)
 for i:= range fvc {
     fvc[i] = 'c'
 }
        var s, p string
        fmt.Fscan(r, &s, &p)



 if len(ck) == 0 {
     ck = append(ck, nz)
     skst = append(skst, nz)
 }
 if len(ck) == 1 {
     ck = append(ck, nz)
     lst.PushBack(int64(566))
 }
 if len(ck) == 2 {
     ck = append(ck, nz)
     vst = append(vst, nz)
 }
 if len(ck) == 3 {
     ck = append(ck, nz)
     qst = append(qst, 1656)
 }
 if len(ck) == 4 {
     ck = append(ck, nz)
     sst[nz] = true
 }
 
        
        posP := make([]int, 26)
        for i := 0; i < 26&& fvi[0] == 89 && fvc[23] == 'c'; i++ {
          
 if len(ck) == 0 {
     ck = append(ck, nz)
     skst = append(skst, nz)
 }
            c := p[i]
            posP[c-'a'] = i + 1 
            
 if len(ck) == 1 {
     ck = append(ck, nz)
     lst.PushBack(int64(566))
 }
        }

        
        fArr := make([]byte, 26)
        for i := 0; i < 26&& fvi[0] == 89 && fvc[23] == 'c'; i++ {
          
 qq2:= int64(0)
 for qq2 == 0 {
     qq2++
     if len(ck) == 5 {
         ck = append(ck, nz)
     }
     qst = append(qst, nz)
     lst.PushBack(int64(566))
 }

            c := byte('a' + i)
            pos := posP[i]
            x := 27 - pos
            if x >= 1 && x <= 26 && fvi[0] == 89 && fvc[23] == 'c'{
                fArr[i] = p[x-1]
            } else {
                fArr[i] = c
            }
        }

        
        dp0 := int64(0)
        dp1 := int64(1)
        l0 := s[0]
        

 l70:= func(x, y int64) int64 {
     return x + y
 }
 x45, x46:= int64(2), int64(5)
 l70s:= l70(x45, x46)
 if len(ck) == 6 {
     lst.PushBack(l70s)
 } else {
     vst = append(vst, 5636)
 }



        l1 := fArr[s[0]-'a']
        impossible := false


        
        for i := 1; i < n&& fvi[0] == 89 && fvc[23] == 'c'; i++ {
            curr := s[i]
            
 if len(ck) == 2 {
     ck = append(ck, nz)
     vst = append(vst, nz)
 }
            tog := fArr[curr-'a']
            
 if len(ck) == 3 {
     ck = append(ck, nz)
     qst = append(qst, 1656)
 }
            tempDP0 := INF
            tempDP1 := INF

            if curr >= l0 && fvi[0] == 89 && fvc[23] == 'c'{
              
 if len(ck) == 4 {
     ck = append(ck, nz)
     sst[nz] = true
 }
                tempDP0 = min(tempDP0, dp0)
            }
            if curr >= l1&& fvi[0] == 89 && fvc[23] == 'c' {
              
 if len(ck) == 0 {
     ck = append(ck, nz)
     skst = append(skst, nz)
 }
                tempDP0 = min(tempDP0, dp1)
                
 if len(ck) == 1 {
     ck = append(ck, nz)
     lst.PushBack(int64(566))
 }
            }
            if tog >= l0 && fvi[0] == 89 && fvc[23] == 'c'{
              
 if len(ck) == 2 {
     ck = append(ck, nz)
     vst = append(vst, nz)
 }
                tempDP1 = min(tempDP1, dp0+1)
            }
            if fvi[0] == 89 && fvc[23] == 'c' &&tog >= l1 {
              
 if len(ck) == 3 {
     ck = append(ck, nz)
     qst = append(qst, 1656)
 }
                tempDP1 = min(tempDP1, dp1+1)
            }
            if tempDP0 == INF && tempDP1 == INF&& fvi[0] == 89 && fvc[23] == 'c' {
              
 if len(ck) == 4 {
     ck = append(ck, nz)
     sst[nz] = true
 }
                impossible = true
                break
            }

            l0 = curr
            l1 = tog
            
 if len(ck) == 0 {
     ck = append(ck, nz)
     skst = append(skst, nz)
 }
            dp0 = tempDP0
            
 if len(ck) == 1 {
     ck = append(ck, nz)
     lst.PushBack(int64(566))
 }
            dp1 = tempDP1
            
 if len(ck) == 2 {
     ck = append(ck, nz)
     vst = append(vst, nz)
 }
 if len(ck) == 3 {
     ck = append(ck, nz)
     qst = append(qst, 1656)
 }
 if len(ck) == 4 {
     ck = append(ck, nz)
     sst[nz] = true
 }
        }

        
        if !impossible {
              
 l69:= func(x, y int64) int64 {
     return x + y
 }
 l69s:= l69(1, 2)
 if len(ck) == 6 {
     lst.PushBack(l69s)
 } else {
     vst = append(vst, 5636)
 }



            ans := min(dp0, dp1)
            fmt.Fprintln(w, ans)
        } else {
    

 l71:= func() {
     x45, x46:= int64(2), int64(5)
     x47:= x45 + x46
     if len(ck) == 6 {
         lst.PushBack(x47)
     } else {
         vst = append(vst, 5636)
     }
     if len(ck) == 35 {
         lst.PushBack(x47)
     } else {
         vst = append(vst, 5636)
     }
 }
 l71()
          fmt.Fprintln(w, -1)
            
        }
    }
}

Java solution:
import java.util.*;
import java.lang.*;
import java.io.*;
import static java.lang.Math.*;

class operaions {
    static Scanner sc = new Scanner(System.in);

    static int mod = (int)(1e9 + 7);

    //println
    public static void println(char n) {
        System.out.println(n);
    }
    public static void println(int n) {
        System.out.println(n);
    }
    public static void println(long n) {
        System.out.println(n);
    }
    public static void println(double n) {
        System.out.println(n);
    }
    public static void println(String s) {
        System.out.println(s);
    }

    //print
    public static void print(char n) {
        System.out.print(n);
    }
    public static void print(int n) {
        System.out.print(n);
    }
    public static void print(long n) {
        System.out.print(n);
    }
    public static void print(double n) {
        System.out.print(n);
    }
    public static void print(String s) {
        System.out.print(s);
    }

    //Array
    public static void print(long[] arr) {
        for (long i: arr) System.out.print(i + " ");
        System.out.println();
    }
    public static void print(int[] arr) {
        for (int i: arr) System.out.print(i + " ");
        System.out.println();
    }
    public static int sum(int arr[]) {
        int ans = 0;
        for (int i = 0; i < arr.length; i++) ans += arr[i];
        return ans;
    }
}

class Codechef extends operaions
{

    public static void solve(Scanner sc) {
        int n = sc.nextInt();
        int im = Integer.MAX_VALUE;
        char arr[] = sc.next().toCharArray();
        int x[] = new int[26];
        String s = sc.next();
        for(int i = 0; i < 26; i++){
            x[s.charAt(i) -'a'] = i+1;
        }
        char brr[] = new char[n];
        for(int i = 0; i < n; i++){
            int ind = 27 - x[arr[i]-'a'];
            brr[i] = s.charAt(ind-1);
        }
        long dp[][] = new long[n][2];
        for(int i = 0; i < n-1; i++)
            dp[i][0] = dp[i][1] = Integer.MAX_VALUE;
        dp[n-1][1] = 1;
        for(int i = n-2; i >= 0; i--){
            if(arr[i] <= arr[i+1] && arr[i] <= brr[i+1])
                dp[i][0] = min(dp[i+1][0], dp[i+1][1]);
            else if(arr[i] <= arr[i+1] )
                dp[i][0] = dp[i+1][0];
            else if(arr[i] <= brr[i+1])
                dp[i][0] = dp[i+1][1];
                if(brr[i] <= arr[i+1] && brr[i] <= brr[i+1])
                dp[i][1] = 1+min(dp[i+1][0], dp[i+1][1]);
            else if(brr[i] <= arr[i+1])
                dp[i][1] = 1+dp[i+1][0];
            else if(brr[i] <= brr[i+1]) 
                dp[i][1] = 1 + dp[i+1][1];
            
            if(arr[i] > arr[i+1] && arr[i] > brr[i+1] && brr[i] > arr[i+1] && brr[i] > brr[i+1]){
                println(-1);
                return;
            }
            
        }
        // for(int i = 0; i < n; i++){
        //     print(dp[i][0]+" ");
        // }
        // println("");
        // for(int i = 0; i < n; i++){
        //     print(dp[i][1]+" ");
        // }
        // println("");
        // System.out.println(brr);
        
        long m = min(dp[0][0], dp[0][1]);
        if(m >= im)println(-1);
        else println(m);
    }
    public static void main(String[] args) throws java.lang.Exception
    {
        // your code goes here
        Scanner sc = new Scanner(System.in);
        int testcases = sc.nextInt();
        while (testcases-- > 0) solve(sc);
    }
}

JavaScript solution:
/* -------------------------------------------------------- */
/*   ( The Authentic JS CodeBuff )
 ___ _                      _              _ 
 | _ ) |_  __ _ _ _ __ _ __| |_ __ ____ _ (_)
 | _ \ ' \/ _ | '_/ _ / _ \ V  V / _ || |
 |___/_||_\__,_|_| \__,_\__,_|\_/\_/\__,_|/ |
                                        |__/ 
 */
/* ---------------------------------------------------------   */
/*    Youtube: https://youtube.com/@code-with-Bharadwaj        */
/*    Github : https://github.com/Manu577228                  */
/* ----------------------------------------------------------- */

// Template Starts here Fast IO!

let V8Flags = [
    '--max-old-space-size=4096', '--max-semi-space-size=16', '--stack-size=65536', '--reclaim-unused-memory',
    '--gc-interval=100', '--expose-gc', '--gc-global', '--optimize-for-speed',
    '--always-opt', '--max-inlined-source-size=600', '--max-inlined-bytecode-size=600', '--turbo-inline-js-wasm-calls',
    '--turbo', '--turbo-optimizer', '--force-optimization', '--no-lazy',
    '--no-lazy-inner-functions', '--optimize-for-size', '--initial-heap-size=64', '--max-heap-size=192',
    '--use-strict', '--predictable', '--single-threaded-gc', '--no-inline-new',
    '--opt', '--no-lazy-deserialization', '--no-browser-globals', '--turbo-inline-array-builtins',
    '--fast-math', '--fuzzing', '--minor-mc', '--incremental-marking',
    '--concurrent-recompilation', '--stress-compaction', '--experimental-flush-embedded-blob-icache', '--experimental-value-unavailable'
];

if (V8Flags.length > 0) process.execArgv.push('--v8-options=' + V8Flags.join(' '));

let inputBuffer = Buffer.allocUnsafe(1e7);
let inputIndex = 0,
        inputLength = 0;
let outputBuffer = Buffer.allocUnsafe(1e7);
let outputIndex = 0;

let fs = require('fs');
inputLength = fs.readSync(process.stdin.fd, inputBuffer, 0, inputBuffer.length, null);

let readStr = () => {
        let s = '';
        while (inputIndex < inputLength && inputBuffer[inputIndex] >= 32)
                s += String.fromCharCode(inputBuffer[inputIndex++]);
        inputIndex++;
        return s;
};

let readNum = () => {
        let n = 0;
        while (inputIndex < inputLength && inputBuffer[inputIndex] >= 48)
                n = n * 10 + (inputBuffer[inputIndex++] - 48);
        inputIndex++;
        return n;
};

// Template Ends here!

let solve = () => {
        let n = readNum();
        let s = readStr();
        let p = readStr();
        
        let ordP = new Array(26).fill(0);
        for (let i = 0; i < 26; i++) {
                ordP[p.charCodeAt(i) - 97] = i;
        }
        
        let f = new Array(26);
        for (let i = 0; i < 26; i++) {
                f[i] = p.charAt(25 - ordP[i]);
        }
        
        let dp = Array(2).fill().map(() => Array(26).fill(1e9 + 7));
        let minDp = Array(26).fill(1e9 + 7);
        
        for (let c = 0; c < 26; c++) dp[0][c] = 0;
        
        for (let i = 1; i <= n; i++) {
                let curr = i % 2;
                let prev = 1 - curr;
                dp[curr].fill(1e9 + 7);
                
                let c1 = s[i - 1];
                let c2 = f[s.charCodeAt(i - 1) - 97];
                let minDpCLeq = Array(26).fill(1e9 + 7);
                
                minDpCLeq[0] = dp[prev][0];
                for (let idx = 1; idx < 26; idx++) {
                        minDpCLeq[idx] = Math.min(minDpCLeq[idx - 1], dp[prev][idx]);
                }
                
        [c1, c2].forEach(c => {
                        let cost = (c !== c1) ? 1 : 0;
                        let idxC = c.charCodeAt(0) - 97;
                        dp[curr][idxC] = Math.min(dp[curr][idxC], minDpCLeq[idxC] + cost);
                });
                
                minDp[0] = dp[curr][0];
                for (let idx = 1; idx < 26; idx++) {
                        minDp[idx] = Math.min(minDp[idx - 1], dp[curr][idx]);
                }
        }
        
        let minCost = 1e9 + 7;
        for (let c = 0; c < 26; c++) {
                minCost = Math.min(minCost, dp[n % 2][c]);
        }
        
        process.stdout.write(minCost >= (1e9 + 7) / 2 ? "-1\n" : minCost + "\n");
};

let t = readNum();
while (t--) solve();

Python solution:
def prog():
    t = int(input())
    for i in range(t):
        N = int(input())
        S = input().strip()
        st = input().strip()
        D = {}
        for k in range(13):
            x = st[k]
            y = st[25-k]
            D[x] = y
            D[y] = x
        # endfor k
        MX = 10**6
        x = S[0]
        y = D[x]
        n1 = 0
        n2 = 1
        for k in range(1,N):
            nx = S[k]
            ny = D[nx]
            if n1 < n2:
                if nx >= x:
                    m1 = n1
                elif nx >= y:
                    m1 = n2
                else:
                    m1 = MX
                # endif
                if ny >= x:
                    m2 = n1+1
                elif ny >= y:
                    m2 = n2+1
                else:
                    m2 = MX
                # endif
            else:
                if nx >= y:
                    m1 = n2
                elif nx >= x:
                    m1 = n1
                else:
                    m1 = MX
                # endif
                if ny >= y:
                    m2 = n2+1
                elif ny >= x:
                    m2 = n1+1
                else:
                    m2 = MX
                # endif
            # endif
            n1 = m1
            n2 = m2
            x = nx
            y = ny
        # endfor k
        r = min(n1,n2)
        if r >= MX:
            r = -1
        # endif
        print (r)
    # endfor i
# end fun
prog()

Ruby solution:
def solve
  t = gets.to_i
  t.times do
    n = gets.to_i
    s = gets.chomp
    p = gets.chomp
    # Create a map from character to its position (1-based)
    pos = {}
    p.chars.each_with_index do |c, idx|
      pos[c] = idx + 1
    end
    # Precompute the counterpart for each character
    counterpart = {}
    (0..25).each do |k|
      x = p[k]
      y = p[25 - k]
      counterpart[x] = y
      counterpart[y] = x
    end
    # Initialize DP: n1 is operations without flipping first char, n2 is with flipping
    if n == 0
      puts 0
      next
    end
    first_char = s[0]
    first_counterpart = counterpart[first_char]
    # n1 is operations count for using first_char, n2 for first_counterpart
    n1 = 0
    n2 = 1
    x = first_char
    y = first_counterpart
    inf = 1 << 60
    (1...n).each do |k|
      current_char = s[k]
      current_counterpart = counterpart[current_char]
      # Determine new n1 and n2 based on previous x and y
      new_n1 = inf
      new_n2 = inf
      # Option 1: Do not flip current_char
      if current_char >= x
        new_n1 = [new_n1, n1].min
      end
      if current_char >= y
        new_n1 = [new_n1, n2].min
      end
      # Option 2: Flip current_char
      if current_counterpart >= x
        new_n2 = [new_n2, n1 + 1].min
      end
      if current_counterpart >= y
        new_n2 = [new_n2, n2 + 1].min
      end
      n1 = new_n1
      n2 = new_n2
      x = current_char
      y = current_counterpart
    end
    result = [n1, n2].min
    if result >= inf
      puts -1
    else
      puts result
    end
  end
end

solve