Python – String uncommon characters

One of the string operation can be computing the uncommon characters of two strings i.e, output the uncommon values that appear in both strings. This article deals with computing the same in different ways. 

Method 1: Using set() + symmetric_difference() Set in python usually can perform the task of performing set operations such as set symmetric difference. This utility of sets can be used to perform this task as well. Firstly, both the strings are converted into sets using set(), and then the symmetric difference is performed using symmetric_difference(). Returns the sorted set. 

The original string 1 is : Lazyroar
The original string 2 is : Codefreaks
The string uncommon elements are : {'a', 'C', 'G', 'd'}

Method 2 : Using join() join() performs the task similar to list comprehension in case of lists. This encapsulates whole symmetric_difference logic and joins together each element filtered through the symmetric_difference logic into one string, hence computing the symmetric_difference. It converts the strings into set and then computed ^ operation on them.

The original string 1 is : Lazyroar
The original string 2 is : Codefreaks
The string uncommon elements are : CGad

The Time and Space Complexity for all the methods are the same:

Time Complexity: O(nlogn)
Auxiliary Space: O(n)

Method #3: Using Counter() function

The original string 1 is : Lazyroar
The original string 2 is : Codefreaks
The string uncommon elements are : ['C', 'G', 'a', 'd']

Time Complexity: O(n*m), where n is length of frequency_str1 and m is length of frequency_str2.

Auxiliary Space: O(n), where n is length of result list.

Method #4: Using numpy:

Algorithm:

1. Import the numpy module.
2. Initialize two strings test_str1 and test_str2.
3. Print the original strings.
4. Convert the strings to lists using list() method.
5. Using numpy setdiff1d() function, compute the difference between the two lists, i.e., uncommon characters in the first list.
6. Similarly, compute the difference for the second list.
7. Concatenate the two results using numpy concatenate() method to get the final uncommon characters
8. Print the uncommon characters.

Output:
The original string 1 is : Lazyroar
The original string 2 is : Codefreaks
The string uncommon elements are : ['G' 'C' 'a' 'd']

Time Complexity: O(m + n log n), where m and n are the lengths of the input strings. Converting the strings to lists takes O(m+n) time. The setdiff1d() function takes O(n log n) time for sorting and O(n) time for finding the unique elements. Therefore, the overall time complexity of this method is O(m + n log n).

Auxiliary Space: O(m + n), where m and n are the lengths of the input strings. Converting the strings to lists takes O(m+n) space. The setdiff1d() function takes O(n) space for creating the output array. Therefore, the overall space complexity of this method is O(m + n).

Method #5:  Using heapq:

Algorithm:

1. Initialize two strings “test_str1” and “test_str2”.
2. Print the initial strings.
3. Find the symmetric difference between two sets of the characters of the given strings using the set difference operator.
4. Merge the resultant sets obtained in step 3 using the heapq.merge() method.
5. Store the merged set in a list.
6. Print the list obtained in step 5 as the output.

The original string 1 is : Lazyroar
The original string 2 is : Codefreaks
The string uncommon elements are : ['G', 'a', 'C', 'd']

Time Complexity:
The time complexity for the set difference operation is O(n), where n is the length of the string. The time complexity of the heapq.merge() method is O(n log n) for n elements. Therefore, the overall time complexity of the algorithm is O(n log n).

Auxiliary Space:
The space complexity of the algorithm is O(n), as we are using sets to store the characters of the given strings and a list to store the merged set.