Número mínimo de manipulaciones requeridas para hacer dos anagramas de strings sin borrar el carácter

Dadas dos strings s1 y s2 , necesitamos encontrar el número mínimo de manipulaciones requeridas para hacer un anagrama de dos strings sin borrar ningún carácter. 

Nota: – Las strings de anagramas tienen el mismo conjunto de caracteres, la secuencia de caracteres puede ser diferente. 

Si se permite la eliminación de caracteres y se indica el costo, consulte Costo mínimo para hacer que dos strings sean idénticas
Pregunta Fuente: Yatra.com Experiencia de la entrevista | conjunto 7 

Ejemplos: 

Input : 
       s1 = "aba"
       s2 = "baa"
Output : 0
Explanation: Both String contains identical characters

Input :
       s1 = "ddcf"
       s2 = "cedk"
Output : 2
Explanation : Here, we need to change two characters
in either of the strings to make them identical. We 
can change 'd' and 'f' in s1 or 'e' and 'k' in s2.

Suposición: la longitud de ambas strings se considera similar 

Implementación:

// C++ Program to find minimum number
// of manipulations required to make
// two strings identical
#include <bits/stdc++.h>
using namespace std;
 
    // Counts the no of manipulations
    // required
    int countManipulations(string s1, string s2)
    {
         
        int count = 0;
 
        // store the count of character
        int char_count[26];
         
        for (int i = 0; i < 26; i++)
        {
            char_count[i] = 0;
        }
 
        // iterate though the first String
        // and update count
        for (int i = 0; i < s1.length(); i++)
            char_count[s1[i] - 'a']++;
 
        // iterate through the second string
        // update char_count.
        // if character is not found in
        // char_count then increase count
        for (int i = 0; i < s2.length(); i++)
        {
            char_count[s2[i] - 'a']--;      
        }
       
        for(int i = 0; i < 26; ++i)
        {
          if(char_count[i] != 0)
          {
            count+=abs(char_count[i]);
          }
        }
        return count / 2;
    }
 
    // Driver code
    int main()
    {
 
        string s1 = "ddcf";
        string s2 = "cedk";
         
        cout<<countManipulations(s1, s2);
    }
  
// This code is contributed by vt_m.

// Java Program to find minimum number of manipulations
// required to make two strings identical
public class Similar_strings {
 
    // Counts the no of manipulations required
    static int countManipulations(String s1, String s2)
    {
        int count = 0;
 
        // store the count of character
        int char_count[] = new int[26];
 
        // iterate though the first String and update
        // count
        for (int i = 0; i < s1.length(); i++)
            char_count[s1.charAt(i) - 'a']++;       
 
        // iterate through the second string
        // update char_count.
        // if character is not found in char_count
        // then increase count
        for (int i = 0; i < s2.length(); i++)
        {
            char_count[s2.charAt(i) - 'a']--;
        }
       
        for(int i = 0; i < 26; ++i)
        {
          if(char_count[i] != 0)
          {
            count+= Math.abs(char_count[i]);
          }
        }
         
        return count / 2;
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        String s1 = "ddcf";
        String s2 = "cedk";
        System.out.println(countManipulations(s1, s2));
    }
}

# Python3 Program to find minimum number
# of manipulations required to make
# two strings identical
 
# Counts the no of manipulations
# required
def countManipulations(s1, s2):
     
    count = 0
 
    # store the count of character
    char_count = [0] * 26
     
    for i in range(26):
        char_count[i] = 0
 
    # iterate though the first String
    # and update count
    for i in range(len( s1)):
        char_count[ord(s1[i]) -
                   ord('a')] += 1
 
    # iterate through the second string
    # update char_count.
    # if character is not found in
    # char_count then increase count
    for i in range(len(s2)):
        char_count[ord(s2[i]) - ord('a')] -= 1
         
    for i in range(26):
        if char_count[i] != 0:
            count += abs(char_count[i])
         
 
    return count / 2
 
# Driver code
if __name__ == "__main__":
 
    s1 = "ddcf"
    s2 = "cedk"
     
    print(countManipulations(s1, s2))
 
# This code is contributed by ita_c

// C# Program to find minimum number
// of manipulations required to make
// two strings identical
using System;
 
public class GFG {
 
    // Counts the no of manipulations
    // required
    static int countManipulations(string s1,
                                  string s2)
    {
        int count = 0;
 
        // store the count of character
        int []char_count = new int[26];
 
        // iterate though the first String
        // and update count
        for (int i = 0; i < s1.Length; i++)
            char_count[s1[i] - 'a']++;
 
        // iterate through the second string
        // update char_count.
        // if character is not found in
        // char_count then increase count
        for (int i = 0; i < s2.Length; i++)
            char_count[s2[i] - 'a']--;
       
        for(int i = 0; i < 26; ++i)
        {
            if(char_count[i] != 0)
            {
              count+= Math.Abs(char_count[i]);
            }
        }
         
        return count / 2;
    }
 
    // Driver code
    public static void Main()
    {
 
        string s1 = "ddcf";
        string s2 = "cedk";
         
        Console.WriteLine(
            countManipulations(s1, s2));
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP Program to find minimum number
// of manipulations required to make
// two strings identical
 
// Counts the no of manipulations
// required
function countManipulations($s1, $s2)
{
    $count = 0;
 
    // store the count of character
    $char_count = array_fill(0, 26, 0);
 
    // iterate though the first String
    // and update count
    for ($i = 0; $i < strlen($s1); $i++)
        $char_count[ord($s1[$i]) -
                    ord('a')] += 1;
 
    // iterate through the second string
    // update char_count.
    // if character is not found in
    // char_count then increase count
    for ($i = 0; $i < strlen($s2); $i++)
    {
        $char_count[ord($s2[$i]) -
                    ord('a')] -= 1;
         
    }
   
    for ($i = 0; $i < 26; $i++)
    {
      if($char_count[i]!=0)
      {
        $count+=abs($char_count[i]);
      }
    }
    return ($count) / 2;
}
 
// Driver code
$s1 = "ddcf";
$s2 = "cedk";
 
echo countManipulations($s1, $s2);
 
// This code is contributed by Ryuga
?>

<script>
 
// Javascript program to find minimum number
// of manipulations required to make
// two strings identical
     
// Counts the no of manipulations
// required
function countManipulations(s1, s2)
{
    let count = 0;
 
    // Store the count of character
    let char_count = new Array(26);
    for(let i = 0; i < char_count.length; i++)
    {
        char_count[i] = 0;
    }
     
    // Iterate though the first String and
    // update count
    for(let i = 0; i < s1.length; i++)
        char_count[s1[i].charCodeAt(0) -
                     'a'.charCodeAt(0)]++;      
 
    // Iterate through the second string
    // update char_count.
    // If character is not found in char_count
    // then increase count
    for(let i = 0; i < s2.length; i++)
    {
        char_count[s2[i].charCodeAt(0) -
                     'a'.charCodeAt(0)]--;
    }
    
    for(let i = 0; i < 26; ++i)
    {
        if (char_count[i] != 0)
        {
            count += Math.abs(char_count[i]);
        }
    }
    return count / 2;
}
 
// Driver code
let s1 = "ddcf";
let s2 = "cedk";
 
document.write(countManipulations(s1, s2));
 
// This code is contributed by avanitrachhadiya2155
     
</script>

2

Complejidad de tiempo: O(n) , donde n es la longitud de la string. 
Espacio Auxiliar: O(1).

Este artículo es aportado por Sumit Ghosh y mejorado por Md Istakhar Ansari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.