Find and print the uncommon characters of the two given strings in sorted order. Here uncommon character means that either the character is present in one string or it is present in other string but not in both. The strings contain only lowercase characters and can contain duplicates.
Examples:
Input: str1 = “characters”, str2 = “alphabets”
Output: b c l p r
Input: str1 = “geeksforgeeks”, str2 = “geeksquiz”
Output: f i o q r u z
Naive Approach: Using two loops, for each character of 1st string check whether it is present in the 2nd string or not. Likewise, for each character of 2nd string check whether it is present in the 1st string or not.
Time Complexity: O(n^2) and extra would be required to handle duplicates.
Efficient Approach: An efficient approach is to use hashing.
Below is the implementation of the above approach:
# 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
Output:
b c l p r
Time Complexity: O(m + n), where m and n are the sizes of the two strings respectively.
Australia
UK
UAE
Singapore
Canada
New
Zealand
Malaysia
USA
India
South
Africa
Ireland
Saudi
Arab
Qatar
Kuwait
Hongkong
Copyright 2016-2023 www.programmingshark.com - All Rights Reserved.
Disclaimer : Any type of help and guidance service given by us is just for reference purpose. We never ask any of our clients to submit our solution guide as it is, anywhere.