Uncommon Characters

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
6 upvotes
Asked in company
SAP Labs

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
coding ninjas
Sample Output 1:
acdgjos
Explanation of the Sample Input 1:
For the given two strings, {c, o, d, g} are the characters that are present only in the first string and {j, s} are characters that are present only in the second string. Thus, {c, o, d, g, j, s} are the uncommon characters for the given two strings and are printed in the sorted order.
Sample Input 2:
2
study dusty
uncommon common
Sample Output 2:
u
Explanation of Sample Input 2
For the first test case, there are no uncommon letters for the two strings. Thus, the output for the first test case is “”. 

For the second test case, ‘u’ is the only uncommon letter.
Hint

For each alphabet (a-z), try to check if it exists in only one of the strings.

Approaches (2)
Naive Approach

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.

Time Complexity

O(N * M), where N and M are lengths of the strings S1 and S2 respectively.

 

The time complexity of finding the characters that are present in one string and not in another using two loops is O(N * M). Also, inserting an element in a set takes O(log(K)) time, where K is the size of the set. Here, the set can have a maximum size of 26, thus the worst case complexity of inserting an element in the set will be O(log(26)). Now, Since we are using the strategy of loops two times, the final complexity is O(2 * N * M * log(26)) = O(N * M).

Space Complexity

O(1).

 

Since the set uncommonChars can contain at most 26 elements (since there are 26 lowercase alphabets), constant additional space is required.

Code Solution
(100% EXP penalty)
Uncommon Characters
Full screen
Console