Costo mínimo para convertir str1 a str2 con las operaciones dadas

Dadas dos strings de igual longitud , str1 y str2 , que constan únicamente de los caracteres ‘a’ y ‘b’ . Las siguientes operaciones se pueden realizar en str1 : 
 

1. Cualquier carácter se puede cambiar de ‘a’ a ‘b’ o de ‘b’ a ‘a’ con 1 costo unitario.
2. Cualquier par de caracteres str1[i] y str1[j] se pueden intercambiar con costo |i – j| .

La tarea es encontrar el costo mínimo requerido para convertir str1 a str2 .
Ejemplos: 
 

Entrada: str1 = “abb”, str2 = “baa” 
Salida: 2 
Intercambiar (str1[0], str1[1]), str1 = “bab” y costo = 1 
Cambiar str1[2] = ‘b’ a ‘a ‘, str1 = “baa” y costo = 2
Entrada: str1 = “abab”, str2 = “aabb” 
Salida: 1 
 

Enfoque: se puede observar que el intercambio solo se realizará en caracteres consecutivos porque si los caracteres no son consecutivos, el costo del intercambio será ≥ 2, lo que dará un costo mayor o igual al costo de cambiar esos caracteres usando la operación de el primer tipo. Ahora, por cada dos caracteres consecutivos si son diferentes en ambas strings, intercambie estos caracteres incurriendo en un costo unitario en comparación con el costo unitario de 2 cuando ambos se cambian por separado. De lo contrario, cambie el carácter que es diferente en ambas strings (ya sea la actual o la siguiente). Finalmente, imprima el costo calculado.
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
// cost to convert str1 to sr2
int minCost(string str1, string str2, int n)
{
    int cost = 0;
 
    // For every character of str1
    for (int i = 0; i < n; i++) {
 
        // If current character is not
        // equal in both the strings
        if (str1[i] != str2[i]) {
 
            // If the next character is also different in both
            // the strings then these characters can be swapped
            if (i < n - 1 && str1[i + 1] != str2[i + 1]) {
                swap(str1[i], str1[i + 1]);
                cost++;
            }
 
            // Change the current character
            else {
                cost++;
            }
        }
    }
    return cost;
}
 
// Driver code
int main()
{
    string str1 = "abb", str2 = "bba";
    int n = str1.length();
 
    cout << minCost(str1, str2, n);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function to return the minimum
// cost to convert str1 to sr2
static int minCost(char []str1,
                   char []str2, int n)
{
    int cost = 0;
 
    // For every character of str1
    for (int i = 0; i < n; i++)
    {
 
        // If current character is not
        // equal in both the strings
        if (str1[i] != str2[i])
        {
 
            // If the next character is also different in both
            // the strings then these characters can be swapped
            if (i < n - 1 && str1[i + 1] != str2[i + 1])
            {
                swap(str1, i, i + 1);
                cost++;
            }
 
            // Change the current character
            else
            {
                cost++;
            }
        }
    }
    return cost;
}
 
static void swap(char []arr, int i, int j)
{
    char temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
 
// Driver code
public static void main(String[] args)
{
    String str1 = "abb", str2 = "bba";
    int n = str1.length();
 
    System.out.println(minCost(str1.toCharArray(),
                               str2.toCharArray(), n));
}
}
 
// This code is contributed by Rajput-Ji

# Python3 implementation of the approach
 
# Function to return the minimum
# cost to convert str1 to sr2
def minCost(str1, str2, n):
 
    cost = 0
 
    # For every character of str1
    for i in range(n):
 
        # If current character is not
        # equal in both the strings
        if (str1[i] != str2[i]):
 
            # If the next character is also different in both
            # the strings then these characters can be swapped
            if (i < n - 1 and str1[i + 1] != str2[i + 1]):
                swap(str1[i], str1[i + 1])
                cost += 1
             
            # Change the current character
            else:
                cost += 1
             
    return cost
 
# Driver code
if __name__ == '__main__':
 
    str1 = "abb"
    str2 = "bba"
    n = len(str1)
 
    print(minCost(str1, str2, n))
 
# This code is contributed by ashutosh450

// C# implementation of the approach
using System;
 
class GFG
{
     
    // Function to return the minimum
    // cost to convert str1 to sr2
    static int minCost(string str1,
                       string str2, int n)
    {
        int cost = 0;
     
        char[] array = str1.ToCharArray();
         
        // For every character of str1
        for (int i = 0; i < n; i++)
        {
     
            // If current character is not
            // equal in both the strings
            if (str1[i] != str2[i])
            {
     
                // If the next character is also different in both
                // the strings then these characters can be swapped
                if (i < n - 1 && str1[i + 1] != str2[i + 1])
                {
                    char temp = array[i];
                    array[i] = array[i + 1];
                    array[i + 1] = temp ;
                     
                    cost++;
                }
     
                // Change the current character
                else
                {
                    cost++;
                }
            }
        }
        return cost;
    }
     
    // Driver code
    static public void Main ()
    {
        string str1 = "abb", str2 = "bba";
        int n = str1.Length;
     
        Console.WriteLine(minCost(str1, str2, n));
    }
}
 
// This code is contributed by AnkitRai01

<script>
    // Javascript implementation of the approach
     
    // Function to return the minimum
    // cost to convert str1 to sr2
    function minCost(str1, str2, n)
    {
        let cost = 0;
       
        let array = str1.split('');
           
        // For every character of str1
        for (let i = 0; i < n; i++)
        {
       
            // If current character is not
            // equal in both the strings
            if (str1[i] != str2[i])
            {
       
                // If the next character is also different in both
                // the strings then these characters can be swapped
                if (i < n - 1 && str1[i + 1] != str2[i + 1])
                {
                    let temp = array[i];
                    array[i] = array[i + 1];
                    array[i + 1] = temp ;
                       
                    cost++;
                }
       
                // Change the current character
                else
                {
                    cost++;
                }
            }
        }
        return cost;
    }
     
    let str1 = "abb", str2 = "bba";
    let n = str1.length;
 
    document.write(minCost(str1, str2, n));
 
// This code is contributed by divyeshrabadiya07.
</script>

2