Encuentra caracteres poco comunes de las dos strings

Encuentre e imprima los caracteres poco comunes de las dos strings dadas en orden ordenado. Aquí carácter poco común significa que el carácter está presente en una string o está presente en otra string pero no en ambas. Las strings contienen solo caracteres en minúsculas y pueden contener duplicados. 
Fuente: experiencia de entrevista de Amazon | Set 355 (para 1 año de experiencia)

Ejemplos: 

Entrada : str1 = «caracteres», str2 = «alfabetos» 
Salida : bclpr
Entrada : str1 = «geeksforgeeks», str2 = «geeksquiz» 
Salida : fioqruz

Enfoque ingenuo: usando dos bucles, para cada carácter de la primera string, verifique si está presente en la segunda string o no. Del mismo modo, para cada carácter de la segunda string, compruebe si está presente en la primera string o no.

Complejidad de tiempo : O (n ^ 2) y más serían necesarios para manejar duplicados.

Enfoque eficiente: un enfoque eficiente es usar hashing . 

• Utilice una tabla hash de tamaño 26 para todos los caracteres en minúsculas.
• Inicialmente, marque la presencia de cada carácter como ‘0’ (lo que indica que el carácter no está presente en ambas strings).
• Atraviese la primera string y marque la presencia de cada carácter de la primera string como ‘1’ (que indica la primera string) en la tabla hash.
• Ahora, atraviesa la segunda cuerda. Para cada carácter de la segunda string, verifique si su presencia en la tabla hash es ‘1’ o no. Si es ‘1’, marque su presencia como ‘-1’ (lo que indica que el carácter es común a ambas strings); de lo contrario, marque su presencia como ‘2’ (que indica la segunda string).

La imagen de abajo es una ejecución en seco del enfoque anterior:

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

// C++ implementation to find the uncommon
// characters of the two strings
#include <bits/stdc++.h>
using namespace std;
 
// size of the hash table
const int MAX_CHAR = 26;
 
// function to find the uncommon characters
// of the two strings
void findAndPrintUncommonChars(string str1, string str2)
{
    // mark presence of each character as 0
    // in the hash table 'present[]'
    int present[MAX_CHAR];
    for (int i=0; i<MAX_CHAR; i++)
        present[i] = 0;
 
    int l1 = str1.size();
    int l2 = str2.size();
 
    // for each character of str1, mark its
    // presence as 1 in 'present[]'
    for (int i=0; i<l1; i++)
        present[str1[i] - 'a'] = 1;
 
    // for each character of str2
    for (int i=0; i<l2; i++)
    {
        // if a character of str2 is also present
        // in str1, then mark its presence as -1
        if (present[str2[i] - 'a'] == 1
            || present[str2[i] - 'a'] == -1)
            present[str2[i] - 'a'] = -1;
 
        // else mark its presence as 2
        else
            present[str2[i] - 'a'] = 2;
    }
 
    // print all the uncommon characters
    for (int i=0; i<MAX_CHAR; i++)
        if (present[i] == 1 || present[i] == 2 )
            cout << (char(i + 'a')) << " ";
}
 
// Driver program to test above
int main()
{
    string str1 = "characters";
    string str2 = "alphabets";
    findAndPrintUncommonChars(str1, str2);
    return 0;
}

// Java implementation to find the uncommon
// characters of the two strings
class GFG
{
 
    // size of the hash table
    static int MAX_CHAR = 26;
 
    // function to find the uncommon
    // characters of the two strings
    static void findAndPrintUncommonChars(String str1,
                                       String str2)
    {
        // mark presence of each character as 0
        // in the hash table 'present[]'
        int present[] = new int[MAX_CHAR];
        for (int i = 0; i < MAX_CHAR; i++)
        {
            present[i] = 0;
        }
 
        int l1 = str1.length();
        int l2 = str2.length();
 
        // for each character of str1, mark its
        // presence as 1 in 'present[]'
        for (int i = 0; i < l1; i++)
        {
            present[str1.charAt(i) - 'a'] = 1;
        }
 
        // for each character of str2
        for (int i = 0; i < l2; i++)
        {
             
            // if a character of str2 is also present
            // in str1, then mark its presence as -1
            if (present[str2.charAt(i) - 'a'] == 1
                || present[str2.charAt(i) - 'a'] == -1)
            {
                present[str2.charAt(i) - 'a'] = -1;
            }
             
            // else mark its presence as 2
            else
            {
                present[str2.charAt(i) - 'a'] = 2;
            }
        }
 
        // print all the uncommon characters
        for (int i = 0; i < MAX_CHAR; i++)
        {
            if (present[i] == 1 || present[i] == 2)
            {
                System.out.print((char) (i + 'a') + " ");
            }
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String str1 = "characters";
        String str2 = "alphabets";
        findAndPrintUncommonChars(str1, str2);
    }
}
 
// This code is contributed by Rajput-JI

# Python 3 implementation to find the
# uncommon characters of the two strings
 
# size of the hash table
MAX_CHAR = 26
 
# function to find the uncommon characters
# of the two strings
def findAndPrintUncommonChars(str1, str2):
     
    # mark presence of each character as 0
    # in the hash table 'present[]'
    present = [0] * MAX_CHAR
    for i in range(0, MAX_CHAR):
        present[i] = 0
 
    l1 = len(str1)
    l2 = len(str2)
     
    # for each character of str1, mark its
    # presence as 1 in 'present[]'
    for i in range(0, l1):
        present[ord(str1[i]) - ord('a')] = 1
         
    # for each character of str2
    for i in range(0, l2):
         
        # if a character of str2 is also present
        # in str1, then mark its presence as -1
        if(present[ord(str2[i]) - ord('a')] == 1 or
           present[ord(str2[i]) - ord('a')] == -1):
            present[ord(str2[i]) - ord('a')] = -1
 
        # else mark its presence as 2
        else:
            present[ord(str2[i]) - ord('a')] = 2
 
    # print all the uncommon characters
    for i in range(0, MAX_CHAR):
        if(present[i] == 1 or present[i] == 2):
            print(chr(i + ord('a')), end = " ")
 
# Driver Code
if __name__ == "__main__":
    str1 = "characters"
    str2 = "alphabets"
    findAndPrintUncommonChars(str1, str2)
 
# This code is contributed
# by Sairahul099

// C# implementation to find the uncommon
// characters of the two strings
using System;
 
class GFG
{
 
    // size of the hash table
    static int MAX_CHAR = 26;
 
    // function to find the uncommon
    // characters of the two strings
    static void findAndPrintUncommonChars(String str1,
                                    String str2)
    {
        // mark presence of each character as 0
        // in the hash table 'present[]'
        int []present = new int[MAX_CHAR];
        for (int i = 0; i < MAX_CHAR; i++)
        {
            present[i] = 0;
        }
 
        int l1 = str1.Length;
        int l2 = str2.Length;
 
        // for each character of str1, mark its
        // presence as 1 in 'present[]'
        for (int i = 0; i < l1; i++)
        {
            present[str1[i] - 'a'] = 1;
        }
 
        // for each character of str2
        for (int i = 0; i < l2; i++)
        {
             
            // if a character of str2 is also present
            // in str1, then mark its presence as -1
            if (present[str2[i] - 'a'] == 1
                || present[str2[i] - 'a'] == -1)
            {
                present[str2[i] - 'a'] = -1;
            }
             
            // else mark its presence as 2
            else
            {
                present[str2[i] - 'a'] = 2;
            }
        }
 
        // print all the uncommon characters
        for (int i = 0; i < MAX_CHAR; i++)
        {
            if (present[i] == 1 || present[i] == 2)
            {
                Console.Write((char) (i + 'a') + " ");
            }
        }
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        String str1 = "characters";
        String str2 = "alphabets";
        findAndPrintUncommonChars(str1, str2);
    }
}
 
// This code is contributed by PrinciRaj1992

<script>
// Javascript implementation to find the uncommon
// characters of the two strings
 
// size of the hash table
var MAX_CHAR = 26;
 
// function to find the uncommon characters
// of the two strings
function findAndPrintUncommonChars(str1, str2)
{
    // mark presence of each character as 0
    // in the hash table 'present[]'
    var present = Array(MAX_CHAR);
    for (var i = 0; i < MAX_CHAR; i++)
        present[i] = 0;
 
    var l1 = str1.length;
    var l2 = str2.length;
 
    // for each character of str1, mark its
    // presence as 1 in 'present[]'
    for (var i = 0; i < l1; i++)
        present[str1[i].charCodeAt(0) - 'a'.charCodeAt(0)] = 1;
 
    // for each character of str2
    for (var i = 0; i < l2; i++)
    {
        // if a character of str2 is also present
        // in str1, then mark its presence as -1
        if (present[str2[i].charCodeAt(0) - 'a'.charCodeAt(0)] == 1
            || present[str2[i].charCodeAt(0) - 'a'.charCodeAt(0)] == -1)
            present[str2[i].charCodeAt(0) - 'a'.charCodeAt(0)] = -1;
 
        // else mark its presence as 2
        else
            present[str2[i].charCodeAt(0) - 'a'.charCodeAt(0)] = 2;
    }
 
    // print all the uncommon characters
    for (var i=0; i<MAX_CHAR; i++)
        if (present[i] == 1 || present[i] == 2 )
            document.write( (String.fromCharCode(i + 'a'.charCodeAt(0))) + " ");
}
 
// Driver program to test above
var str1 = "characters";
var str2 = "alphabets";
findAndPrintUncommonChars(str1, str2);
 
// This code is contributed by importantly.
</script>

b c l p r 

Complejidad de tiempo: O(m + n), donde m y n son los tamaños de las dos strings respectivamente.
Espacio auxiliar: O(26), no se requiere ningún otro espacio adicional, por lo que es una constante.

Este artículo es una contribución de Ayush Jauhari . 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.

Otro enfoque basado en mapas:

• Tome dos mapas e inicialice su valor como 0. 
• recorrer la primera string, para cada carácter presente en la primera string, establezca 1 en el primer mapa.
• Haz lo mismo para la segunda cuerda también.
• Iterar a través de los 26 caracteres, si el xor del mapa 1 y el mapa 2 es 1, entonces está presente solo en una de las strings. es decir, esos personajes son personajes poco comunes. Agréguelos en la string de resultados.
• devuelve la string de resultado, si la string está vacía, devuelve -1.

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

#include<bits/stdc++.h>
using namespace std;
 
string UncommonChars(string a, string b)
{
    int mp1[26] = {0}, mp2[26] = {0};
    int n = a.size(), m = b.size();
 
    for(auto &x: a){
      mp1[x-'a'] = 1;
    }
 
    for(auto &x: b){
      mp2[x-'a'] = 1;
    }
 
    string chars = "";
 
    for(int i = 0; i < 26; ++i){
      if(mp1[i]^mp2[i])
        chars+=char(i+'a');
    }
    if(chars == "")
      return "-1";
    else
      return chars;
}
 
int main(){
    string a = "geeksforgeeks";
    string b = "geeksquiz";
    string result = UncommonChars(a,b);
    cout << result << endl;
    return 0;
}

// Java implementation to find the uncommon
// characters of the two strings
class GFG {
 
    // size of the hash table
    static int MAX_CHAR = 26;
 
    // function to find the uncommon
    // characters of the two strings
    static String UncommonChars(String a, String b)
    {
        int mp1[] = new int[MAX_CHAR];
        int mp2[] = new int[MAX_CHAR];
        int n = a.length();
        int m = b.length();
        for (int i = 0; i < n; i++) {
            mp1[a.charAt(i) - 'a'] = 1;
        }
        for (int i = 0; i < m; i++) {
            mp2[b.charAt(i) - 'a'] = 1;
        }
 
        String chars = "";
        for (int i = 0; i < 26; i++) {
            if ((mp1[i] ^ mp2[i]) != 0) {
                chars += (char)(i + 'a');
            }
        }
        if (chars == "")
            return "-1";
        else
            return chars;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String a = "geeksforgeeks";
        String b = "geeksquiz";
        String result = UncommonChars(a, b);
        System.out.print(result);
    }
}
 
// This code is contributed by Aarti_Rathi

using System;
 
public static class GFG {
  public static string UncommonChars(string a, string b)
  {
    int[] mp1 = new int[26];
    int[] mp2 = new int[26];
    int n = a.Length;
    int m = b.Length;
 
    foreach(var x in a) { mp1[x - 'a'] = 1; }
 
    foreach(var x in b) { mp2[x - 'a'] = 1; }
 
    string chars = "";
 
    for (int i = 0; i < 26; ++i) {
      if ((mp1[i] ^ mp2[i]) != 0) {
        chars += (char)(i + 'a');
      }
    }
    if (chars == "") {
      return "-1";
    }
    else {
      return chars;
    }
  }
 
  public static void Main()
  {
    string a = "geeksforgeeks";
    string b = "geeksquiz";
    string result = UncommonChars(a, b);
    Console.Write(result);
    Console.Write("\n");
  }
}
 
// This code is contributed by Aarti_Rathi

fioqruz

Complejidad de tiempo: O(m+n) Donde m es la longitud de la primera string y n es la longitud de la segunda string.
Espacio auxiliar: O(26) , no se requiere ningún otro espacio adicional, por lo que es una constante.

Este enfoque es aportado por Aarti_Rathi y Bibhash Ghosh .