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++
// 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
// 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
# 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#
// 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 // 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 ?>
Javascript
<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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA