Convierta los caracteres de la string 1 en caracteres presentes en la string 2 aumentando o disminuyendo lexicográficamente

Dadas dos strings A y B que tienen alfabetos ingleses en minúsculas, la tarea es encontrar el número de operaciones requeridas para convertir la string A de modo que solo contenga letras que también están en la string B donde en cada operación, se puede cambiar el carácter actual al carácter siguiente o al carácter anterior. Además, el siguiente carácter después de ‘ z ‘ es ‘ a ‘ y el carácter anterior después de ‘ a ‘ es ‘ z ‘.

Ejemplos :

Entrada : A = «abcd», B = «bc»
Salida : 2
Explicación: La string dada A = «abcd» se puede convertir en la string «bbcc» incrementando el primer carácter de la string en el primer movimiento y disminuyendo el último personaje en el segundo movimiento. Por lo tanto, A = “bbcc” tiene todos los caracteres que también están en la string B. Por lo tanto, el número de movimientos requerido es 2, que es el mínimo posible.

Entrada : A = “abcde”, B = “yg”
Salida : 14

Enfoque: El problema dado se puede resolver utilizando un enfoque codicioso . La idea es convertir todos los caracteres de la string A que no están en la string B en el carácter más cercano posible que existe en la string B, lo que se puede hacer siguiendo los pasos a continuación:

• Almacene la frecuencia de los caracteres de la string B en un mapa desordenado m.
• Itere a través de la string A dada y verifique para cada carácter en B , la cantidad de pasos necesarios para convertir el carácter actual en él.
• Las formas de convertir un carácter x a y pueden ser de dos tipos diferentes de la siguiente manera:
  • El primero ^es incrementar el carácter x hasta llegar a y , es decir, rotación en el sentido de las agujas del reloj.
  • La ^2ª es decrementar el carácter x hasta llegar a y , es decir, en sentido contrario a las agujas del reloj.
• Por lo tanto, mantenga la suma de todos los mínimos de los movimientos en sentido horario y antihorario para cada carácter en A, en una variable ans , que es el valor requerido.

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

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate minimum number
// of operations required to convert A
// such that it only contains letters
// in the string B
int minOperations(string a, string b)
{
    // Stores the characters in string B
    unordered_map<char, int> m;
    for (int i = 0; i < b.size(); i++) {
        m[b[i]]++;
    }
 
    // Stores the min count of operations
    int ans = 0;
 
    // Loop to iterate the given array
    for (int i = 0; i < a.size(); i++) {
 
        // Stores the minimum number of
        // moves required for ith index
        int mn = INT_MAX;
 
        // Loop to calculate the number
        // of moves required to convert
        // the current index
        for (int j = 0; j < 26; j++) {
            int val = a[i] - 'a';
 
            // If the current character
            // is also in b
            if (m[a[i]] > 0) {
                mn = 0;
                break;
            }
            else if (m['a' + j] > 0) {
 
                // Minimum of abs(val - j),
                // clockwise rotation and
                // anti clockwise rotation
                mn = min(mn, min(abs(val - j),
                                 min((26 - val) + j,
                                     val + (26 - j))));
            }
        }
 
        // Update answer
        ans += mn;
    }
 
    // Return Answer
    return ans;
}
 
int main()
{
    string A = "abcde";
    string B = "yg";
 
    cout << minOperations(A, B);
 
    return 0;
}

// Java implementation of the above approach
import java.util.*;
class GFG
{
 
// Function to calculate minimum number
// of operations required to convert A
// such that it only contains letters
// in the String B
static int minOperations(String a, String b)
{
   
    // Stores the characters in String B
    HashMap<Character,Integer> m = new HashMap<Character,Integer>();
    for (int i = 0; i < b.length(); i++) {
         if(m.containsKey(b.charAt(i))){
                m.put(b.charAt(i), m.get(b.charAt(i))+1);
            }
            else{
                m.put(b.charAt(i), 1);
            }
    }
 
    // Stores the min count of operations
    int ans = 0;
 
    // Loop to iterate the given array
    for (int i = 0; i < a.length(); i++) {
 
        // Stores the minimum number of
        // moves required for ith index
        int mn = Integer.MAX_VALUE;
 
        // Loop to calculate the number
        // of moves required to convert
        // the current index
        for (int j = 0; j < 26; j++) {
            int val = a.charAt(i) - 'a';
 
            // If the current character
            // is also in b
            if (m.containsKey(a.charAt(i))&&m.get(a.charAt(i)) > 0) {
                mn = 0;
                break;
            }
            else if (m.containsKey((char)('a' + j))&&m.get((char)('a' + j)) > 0) {
 
                // Minimum of Math.abs(val - j),
                // clockwise rotation and
                // anti clockwise rotation
                mn = Math.min(mn, Math.min(Math.abs(val - j),
                                 Math.min((26 - val) + j,
                                     val + (26 - j))));
            }
        }
 
        // Update answer
        ans += mn;
    }
 
    // Return Answer
    return ans;
}
 
public static void main(String[] args)
{
    String A = "abcde";
    String B = "yg";
 
    System.out.print(minOperations(A, B));
 
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation of the above approach
INT_MAX = 2147483647
 
# Function to calculate minimum number
# of operations required to convert A
# such that it only contains letters
# in the string B
def minOperations(a, b):
     
    # Stores the characters in string B
    m = {}
    for i in range(0, len(b)):
        if b[i] in m:
            m[b[i]] += 1
        else:
            m[b[i]] = 1
 
    # Stores the min count of operations
    ans = 0
 
    # Loop to iterate the given array
    for i in range(0, len(a)):
         
        # Stores the minimum number of
        # moves required for ith index
        mn = INT_MAX
 
        # Loop to calculate the number
        # of moves required to convert
        # the current index
        for j in range(0, 26):
            val = ord(a[i]) - ord('a')
 
            # If the current character
            # is also in b
            if (a[i] in m and m[a[i]] > 0):
                mn = 0
                break
 
            elif (chr(ord('a') + j) in m and m[chr(ord('a') + j)] > 0):
                 
                # Minimum of abs(val - j),
                # clockwise rotation and
                # anti clockwise rotation
                mn = min(mn, min(abs(val - j),
                                 min((26 - val) + j,
                               val + (26 - j))))
 
        # Update answer
        ans += mn
 
    # Return Answer
    return ans
 
# Driver code
if __name__ == "__main__":
 
    A = "abcde"
    B = "yg"
 
    print(minOperations(A, B))
 
# This code is contributed by rakeshsahni

// C# implementation of the above approach
using System;
using System.Collections.Generic;
class GFG
{
 
    // Function to calculate Minimum number
    // of operations required to convert A
    // such that it only contains letters
    // in the String B
    static int MinOperations(String a, String b)
    {
 
        // Stores the characters in String B
        Dictionary<char, int> m = new Dictionary<char, int>();
        for (int i = 0; i < b.Length; i++)
        {
            if (m.ContainsKey(b[i]))
            {
                m[b[i]] += 1;
            }
            else
            {
                m[b[i]] = 1;
            }
        }
 
        // Stores the Min count of operations
        int ans = 0;
 
        // Loop to iterate the given array
        for (int i = 0; i < a.Length; i++)
        {
 
            // Stores the Minimum number of
            // moves required for ith index
            int mn = int.MaxValue;
 
            // Loop to calculate the number
            // of moves required to convert
            // the current index
            for (int j = 0; j < 26; j++)
            {
                int val = a[i] - 'a';
 
                // If the current character
                // is also in b
                if (m.ContainsKey(a[i]) && m[a[i]] > 0)
                {
                    mn = 0;
                    break;
                }
                else if (m.ContainsKey((char)('a' + j)) && m[(char)('a' + j)] > 0)
                {
 
                    // Minimum of Math.abs(val - j),
                    // clockwise rotation and
                    // anti clockwise rotation
                    mn = Math.Min(mn, Math.Min(Math.Abs(val - j),
                                     Math.Min((26 - val) + j,
                                         val + (26 - j))));
                }
            }
 
            // Update answer
            ans += mn;
        }
 
        // Return Answer
        return ans;
    }
 
    public static void Main()
    {
        String A = "abcde";
        String B = "yg";
 
        Console.Write(MinOperations(A, B));
 
    }
}
 
// This code is contributed by gfgking

<script>
 
       // JavaScript Program to implement
       // the above approach
 
       // Function to calculate minimum number
       // of operations required to convert A
       // such that it only contains letters
       // in the string B
       function minOperations(a, b)
       {
        
           // Stores the characters in string B
           let m = new Map();
           for (let i = 0; i < b.length; i++)
           {
               if (m.has(b[i])) {
                   m.set(b[i], m.get(b[i]) + 1);
               }
               else {
                   m.set(b[i], 1);
               }
           }
            
           // Stores the min count of operations
           let ans = 0;
            
           // Loop to iterate the given array
           for (let i = 0; i< a.length; i++)
           {
            
               // Stores the minimum number of
               // moves required for ith index
               let mn = 999999;
                
               // Loop to calculate the number
               // of moves required to convert
               // the current index
               for (let j = 0; j< 26; j++)
               {
                
                   let val = a[i].charCodeAt(0) - 'a'.charCodeAt(0);
                    
                   // If the current character
                   // is also in b
                   if (m.get(a[i]) > 0) {
                       mn = 0;
                       break;
                   }
                   else if (m.has(String.fromCharCode('a'.charCodeAt(0) + j))
                       && m.get(String.fromCharCode('a'.charCodeAt(0) + j)) > 0)
                   {
                    
                       // Minimum of abs(val - j),
                       // clockwise rotation and
                       // anti clockwise rotation
                       mn = Math.min(mn, Math.min(Math.abs(val - j),
                           Math.min((26 - val) + j,
                               val + (26 - j))));
                   }
               }
                
               // Update answer
               ans += mn;
           }
            
           // Return Answer
           return ans;
       }
       let A = "abcde";
       let B = "yg";
       document.write(minOperations(A, B));
 
   // This code is contributed by Potta Lokesh
   </script>

14

Complejidad temporal : O(N)
Espacio auxiliar: O(1)