Hashing: Given 2 strings, find uncommon characters

Problem Statement:

You are given 2 strings, you need to find the uncommon characters between 2 strings.

Example:

Input:

S1 = [abcde]
S2 = [abc]

Output: e, d

Solution 1: Bruteforce approach

In this approach, we will use 2 nested loops.

Outer loop will be for S1, inner loop will be for S2 and store the uncommon elements.

Then reverse the loops, outside will be for s2 and inside will be for s1 and store the uncommon elements.

Then return the result.

Time Complexity: O(n*m)
Space Complexity: O(256)

Solution 2: Hashing approach

We will use map to solve the problem.

We insert the char of first string into the map, insert it with 1.

Then iterate over the second string and check if the character is already present or not, if the char is present assign 0, else insert the char with 1.

Iterate through the map again and print the values with 1.

Time Complexity: O(n+m)
Space Complexity: O(256)

Code Solution

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <unordered_map>
#include <map>

using namespace std;

const int MAX_CHAR = 26;

string solution_1(string &s1, string &s2) 
{
  
    string result = "";
    vector<bool> check(MAX_CHAR, false);

    //check s1 in s2
    for (int i = 0; i < s1.size(); i++) 
    {
        bool found = false;

        for (int j = 0; j < s2.size(); j++) 
        {
            if (s1[i] == s2[j]) 
            {
                found = true;
                break;
            }
        }

        if (!found && !check[s1[i] - 'a']) 
        {
            check[s1[i] - 'a'] = true;
            result.push_back(s1[i]);
        }
    }

    //check s2 in s1
    for (int i = 0; i < s2.size(); i++) 
    {
      
        bool found = false;

        for (int j = 0; j < s1.size(); j++) 
        {
            if (s2[i] == s1[j]) 
            {
                found = true;
                break;
            }
        }

        if (!found && !check[s2[i] - 'a']) 
        {
            check[s2[i] - 'a'] = true;
            result.push_back(s2[i]);
        }
    }

    sort(result.begin(), result.end());
    return result;
}


void solution_2(string s1, string s2)
{
   map<char, int> result;

   for (int i = 0; i < s1.size(); ++i)
   {
      result.insert({s1[i], 1});
   }

   for (int i = 0; i < s2.size(); ++i)
   {
      if (result.count(s2[i])) 
      {
         result.find(s2[i])->second = 0;
      }
      else 
      {
         result.insert({s2[i], 1});
      }
   }

   for (auto item: result)
   {
      if (item.second == 1) 
      {
         cout << item.first << " ";
      }
   }
}


int main() 
{
    string s1 = "abcde";
    string s2 = "abc";

    cout << solution_1(s1, s2)<<endl;
    solution_2(s1, s2);
    return 0;
}

Output

de
d e