Last Updated: 14 Oct, 2020
Uncommon Characters
Moderate
Asked in company
Given two strings S1 and S2 of lowercase alphabets, find the list of uncommon characters for the two strings.
A character is uncommon if it is present only in one of the strings i.e. it is either present in S1 or S2, but not in both.
Note :
1. Both the strings contain only lowercase alphabets and can contain duplicates.
2. Return the uncommon characters in lexicographically sorted order.
Input Format
The first line of input contains an integer 'T' representing the number of test cases. Then the test cases follow.
The only line of each test case contains two strings, S1 and S2, separated by a single space.
Output Format:
For each test case, the uncommon characters are printed in sorted order.
The output for each test case is in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= |S1|, |S2| <= 50000
Where |S1| and |S2| are the lengths of the strings S1 and S2 respectively.
Time Limit: 1 sec
Approaches
The basic solution for this problem involves using loops. We use a set, uncommonChars, to store the uncommon characters of the strings as this would reduce our effort on handling duplicates of a single uncommon alphabet (because a set does not contain duplicates). We solve the problem in two parts :
- Finding the uncommon characters that are present in string S1, but not in string S2 :
For every character in string S1, we check if that character is present in string S2 or not. This can be easily done using two loops. If the character is not present in S2, we add it to the set uncommonChars.
- Finding the uncommon characters that are present in string S2, but not in string S1 :
Similarly, for every character in string S2, we check if that character is present in string S1 or not. If the character is not present in S1, we add it to the set uncommonChars.
After the above 2 steps, the set uncommonChars will contain all the uncommon characters for both the strings.
The main idea behind this approach is to use hashing. We create a hash table of size 26 for all the lowercase alphabets and initialize all the elements as 0. Here, 0 denotes that the character is not present is either of the strings.
Now, we start traversing the first string and for every character, we update its value in the hash table as 1. Here, 1 indicates that the character is present in the first string.
After the above step, we start traversing the second string. For each character in the second string, we do the following:
- If its value in the hash table is 1, then this means that the character is present in both the strings. In this case, we set the value in the hash table as -1, where -1 denotes that the character is present in both the strings.
- If its value is 0, then it means that the character is present only in the second string. In this case, we set its value in the hash table as 2, indicating that the character is present only in string 2.
- If its value is 2 or -1, then it means that the character has already been encountered in the second string earlier. In this case, nothing else needs to be done.
Now, the characters that have a value as 1 or 2 in the hash table are the uncommon characters for the given two strings.