Encuentre la cantidad mínima de movimientos de preprocesamiento necesarios para hacer que dos strings sean iguales

Dadas dos strings A y B de igual longitud que consisten en letras minúsculas en inglés. La tarea es contar el número mínimo de movimientos de preprocesamiento en la string A necesarios para que sea igual a la string B después de aplicar las siguientes operaciones: 

1. Elija cualquier índice i (0 ≤ i < n) e intercambie los caracteres a _i y b _i .
2. Elija cualquier índice i (0 ≤ i < n) e intercambie los caracteres a _i y a _{n – i – 1} .
3. Elija cualquier índice i (0 ≤ i < n) e intercambie los caracteres b _i y b _{n – i – 1} .

En un movimiento previo al proceso, puede reemplazar un carácter en A con cualquier otro carácter del alfabeto inglés.

Ejemplos:  

Entrada: A = “abacaba”, B = “bacabaa” 
Salida: 4 
movimientos de preprocesamiento son los siguientes: 
Establecer A ₀ = ‘b’, A ₂ = ‘c’, A ₃ = ‘a’ y A ₄ = ‘b’ y A se convierte en “bbcabba”. 
Entonces podemos obtener strings iguales mediante la siguiente secuencia de operaciones: 
swap(A ₁ , B ₁ ) y swap(A ₁ , A ₅ ).

Entrada: A = “zcabd” B = “dbacz” 
Salida: 0 
No se requieren movimientos de preprocesamiento. 
Podemos usar la siguiente secuencia de cambios para igualar A y B: 
swap(B ₀ , B ₄ ) luego swap(A ₁ , A ₃ ). 
 

Enfoque: dividamos todos los caracteres de ambas strings en grupos de tal manera que los caracteres de cada grupo se puedan intercambiar entre sí con cambios. Entonces, habrá los siguientes grupos: {A ₀ , A _{n – 1} , B ₀ , B _{n – 1} }, {A ₁ , A _{n – 2} , B ₁ , B _{n – 2} } y así sucesivamente. Dado que estos grupos no se afectan entre sí, podemos calcular el número de movimientos de preprocesamiento en cada grupo y luego resumirlo.
¿Cómo determinar si un grupo no necesita ningún movimiento de preprocesamiento? 

Para un grupo que consta de 2 caracteres (habrá uno de esos grupos si n es impar) eso es fácil: si los caracteres de este grupo son iguales, la respuesta es 0; de lo contrario, es 1.

Para determinar el número requerido de movimientos de preprocesamiento para un grupo que consta de cuatro personajes, podemos usar el siguiente hecho: este grupo no requiere ningún movimiento de preprocesamiento si los personajes de este grupo se pueden dividir en pares. Entonces, si el grupo contiene cuatro caracteres iguales o dos pares de caracteres iguales, entonces la respuesta para este grupo es 0. De lo contrario, podemos verificar que reemplazar solo un carácter de A i y A n – i – ₁ será _suficiente . Si es así, entonces la respuesta es 1, de lo contrario, es 2.

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum number of
// pre-processing moves required on string A
int Preprocess(string A, string B)
{
    // Length of the given strings
    int n = A.size();
 
    // To store the required answer
    int ans = 0;
 
    // Run a loop upto n/2
    for (int i = 0; i < n / 2; i++) {
 
        // To store frequency of 4 characters
        map<char, int> mp;
        mp[A[i]]++;
        mp[A[n - i - 1]]++;
        mp[B[i]]++;
        mp[B[n - i - 1]]++;
        int sz = mp.size();
 
        // If size is 4
        if (sz == 4)
            ans += 2;
 
        // If size is 3
        else if (sz == 3)
            ans += 1 + (A[i] == A[n - i - 1]);
 
        // If size is 2
        else if (sz == 2)
            ans += mp[A[i]] != 2;
    }
 
    // If n is odd
    if (n % 2 == 1 && A[n / 2] != B[n / 2])
        ans++;
 
    return ans;
}
 
// Driver code
int main()
{
    string A = "abacaba", B = "bacabaa";
    cout << Preprocess(A, B);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
    // Function to return the minimum number of
    // pre-processing moves required on string A
    static int Preprocess(String A, String B)
    {
        // Length of the given strings
        int n = A.length();
     
        // To store the required answer
        int ans = 0;
     
        // Run a loop upto n/2
        for (int i = 0; i < n / 2; i++)
        {
     
            // To store frequency of 4 characters
             
            HashMap<Character, Integer> mp = new HashMap<>();
             
            if(mp.containsKey(A.charAt(i)))
                mp.put(A.charAt(i), mp.get(A.charAt(i))+1);
            else
            mp.put(A.charAt(i), 1);
             
            if(mp.containsKey(A.charAt(n-i-1)))
                mp.put(A.charAt(n-i-1), mp.get(A.charAt(n-i-1))+1);
            else
            mp.put(A.charAt(n-i-1), 1);
             
            if(mp.containsKey(B.charAt(i)))
                mp.put(B.charAt(i), mp.get(B.charAt(i))+1);
            else
            mp.put(B.charAt(i), 1);
         
            if(mp.containsKey(B.charAt(n-i-1)))
                mp.put(B.charAt(n-i-1), mp.get(B.charAt(n-i-1))+1);
            else
            mp.put(B.charAt(n-i-1), 1);
         
            int sz = mp.size();
     
            // If size is 4
            if (sz == 4)
                ans += 2;
     
            // If size is 3
            else if (sz == 3)
                ans += 1 + (A.charAt(i) == A.charAt(n - i - 1) ? 1 : 0 );
     
            // If size is 2
            else if (sz == 2)
                ans += mp.get(A.charAt(i)) != 2 ? 1 : 0;
        }
     
        // If n is odd
        if (n % 2 == 1 && A.charAt(n / 2) != B.charAt(n / 2))
            ans++;
     
        return ans;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        String A = "abacaba", B = "bacabaa";
        System.out.println(Preprocess(A, B));
     
    }
 
}
 
// This code is contributed by ihritik

# Python3 implementation of the approach
 
# Function to return the minimum number of
# pre-processing moves required on string A
def Preprocess(A, B):
 
    # Length of the given strings
    n = len(A)
 
    # To store the required answer
    ans = 0
 
    # Run a loop upto n/2
    for i in range(n // 2):
 
        # To store frequency of 4 characters
        mp = dict()
         
        mp[A[i]] = 1
        if A[i] == A[n - i - 1]:
            mp[A[n - i - 1]] += 1
 
        if B[i] in mp.keys():
            mp[B[i]] += 1
        else:
            mp[B[i]] = 1
         
        if B[n - i - 1] in mp.keys():
            mp[B[n - 1 - i]] += 1
        else:
            mp[B[n - 1 - i]] = 1
 
        sz = len(mp)
 
        # If size is 4
        if (sz == 4):
            ans += 2
         
        # If size is 3   
        elif (sz == 3):
            ans += 1 + (A[i] == A[n - i - 1])
         
        # If size is 2
        elif (sz == 2):
            ans += mp[A[i]] != 2
     
    # If n is odd
    if (n % 2 == 1 and A[n // 2] != B[n // 2]):
        ans += 1
 
    return ans
 
# Driver code
A = "abacaba"
B = "bacabaa"
print(Preprocess(A, B))
 
# This code is contributed by Mohit Kumar

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
    // Function to return the minimum number of
    // pre-processing moves required on string A
    static int Preprocess(string A, string B)
    {
        // Length of the given strings
        int n = A.Length;
     
        // To store the required answer
        int ans = 0;
     
        // Run a loop upto n/2
        for (int i = 0; i < n / 2; i++)
        {
     
            // To store frequency of 4 characters
             
            Dictionary<char, int> mp = new Dictionary<char, int>();
 
             
            if(mp.ContainsKey(A[i]))
                mp[A[i]]++;
            else
            mp[A[i]] = 1;
             
            if(mp.ContainsKey(A[n-i-1]))
                mp[A[n - i - 1]]++;
            else
                mp[A[n - i - 1]] = 1;
             
             
            if(mp.ContainsKey(B[i]))
                mp[B[i]]++;
            else
            mp[B[i]] = 1;
             
            if(mp.ContainsKey(B[n-i-1]))
                mp[B[n - i - 1]]++;
            else
                mp[B[n - i - 1]] = 1;
             
            int sz = mp.Count;
     
            // If size is 4
            if (sz == 4)
                ans += 2;
     
            // If size is 3
            else if (sz == 3)
                ans += 1 + (A[i] == A[n - i - 1] ? 1 : 0 );
     
            // If size is 2
            else if (sz == 2)
                ans += mp[A[i]] != 2 ? 1 : 0;
        }
     
        // If n is odd
        if (n % 2 == 1 && A[n / 2] != B[n / 2])
            ans++;
     
        return ans;
    }
     
    // Driver code
    public static void Main ()
    {
        string A = "abacaba", B = "bacabaa";
        Console.WriteLine(Preprocess(A, B));
     
    }
}
 
// This code is contributed by ihritik

<?php
// PHP implementation of the approach
 
// Function to return the minimum number of
// pre-processing moves required on string A
function Preprocess($A, $B)
{
     
    // Length of the given strings
    $n = strlen($A);
 
    // To store the required answer
    $ans = 0;
 
    // To store frequency of 4 characters
    $mp = array();
     
    for($i = 0; $i < $n ; $i++)
        $mp[$A[$i]] = 0;
             
    // Run a loop upto n/2
    for ($i = 0; $i < floor($n / 2); $i++)
    {
        $mp[$A[$i]]++;
        $mp[$A[$n - $i - 1]]++;
        $mp[$B[$i]]++;
        $mp[$B[$n - $i - 1]]++;
        $sz = sizeof($mp);
 
        // If size is 4
        if ($sz == 4)
            $ans += 2;
 
        // If size is 3
        else if ($sz == 3)
            if($A[$i] == $A[$n - $i - 1])
                $ans += 1;
            else
                $ans += 1;
 
        // If size is 2
        else if ($sz == 2)
            $ans += $mp[$A[$i]] != 2;
    }
     
    // If n is odd
    if ($n % 2 == 1 && ($A[floor($n / 2)] !=
                        $B[floor($n / 2)]))
        $ans++;
 
    return $ans;
}
 
// Driver code
$A = "abacaba";
$B = "bacabaa";
echo Preprocess($A, $B);
 
// This code is contributed by Ryuga
?>

<script>
 
// Javascript implementation of the approach
 
// Function to return the minimum number of
// pre-processing moves required on string A
function Preprocess(A, B)
{
     
    // Length of the given strings
    let n = A.length;
   
    // To store the required answer
    let ans = 0;
   
    // Run a loop upto n/2
    for(let i = 0; i < n / 2; i++)
    {
         
        // To store frequency of 4 characters
        let mp = new Map();
           
        if (mp.has(A[i]))
            mp.set(A[i], mp.get(A[i]) + 1);
        else
        mp.set(A[i], 1);
           
        if (mp.has(A[n - i - 1]))
            mp.set(A[n - i - 1],
            mp.get(A[n - i - 1]) + 1);
        else
            mp.set(A[n - i - 1], 1);
           
        if (mp.has(B[i]))
            mp.set(B[i], mp.get(B[i]) + 1);
        else
            mp.set(B[i], 1);
       
        if (mp.has(B[n - i - 1]))
            mp.set(B[n - i - 1],
            mp.get(B[n - i - 1]) + 1);
        else
            mp.set(B[n - i - 1], 1);
       
        let sz = mp.size;
   
        // If size is 4
        if (sz == 4)
            ans += 2;
   
        // If size is 3
        else if (sz == 3)
            ans += 1 + (A[i] ==
             A[n - i - 1] ? 1 : 0);
   
        // If size is 2
        else if (sz == 2)
            ans += mp.get(A[i]) != 2 ? 1 : 0;
    }
   
    // If n is odd
    if (n % 2 == 1 && A[Math.floor(n / 2)] !=
                      B[Math.floor(n / 2)])
        ans++;
   
    return ans;
}
 
// Driver code
let A = "abacaba", B = "bacabaa";
document.write(Preprocess(A, B));
 
// This code is contributed by unknown2108
 
</script>

4