Python program to display the letters in the first string but not in the second can be done by taking two sets and subtracting them. As sets support the difference operator, one set could contain the letters of the first string and another set could contain the letters of the second string and when subtracted we could obtain the desired result.
Examples:
Input: set1 = { ‘r’, ‘o’, ‘h’, ‘a’, ‘n’}, set2 = { ‘r’, ‘i’, ‘t’, ‘i’, ‘k’, ‘a’}
Output: set1 – set2 = { ‘o’, ‘h’, ‘n’}Input: a = { ‘g’, ‘e’, ‘e’, ‘k’, ‘s’, ‘f’, ‘o’, ‘r’}, b = { ‘g’, ‘e’, ‘e’, ‘k’, ‘s’}
Output: c = a – b = { ‘f’, ‘o’, ‘r’}
Approach:
Create two sets A and B having characters of first and second string respectively, and take the difference of set A and B to get the answer.
Follow the steps below to Implement the Idea:
- Take two strings, say, a and b
- Convert that strings into sets, say, setA and setB
- Subtract setB from setA
- Print the result
Below is the Implementation of the above approach:
Example 1:
Python3
# string 1a = "neveropen"# string 2b = "Lazyroar"# convert string 1 into setsetA = set(a)# convert string 2 into setsetB = set(b)# store the difference in form of listresult = setA-setB# print resultprint(result) |
{'r', 'f', 'o'}
Time Complexity: O(N), conversion to set takes O(n)
Auxiliary Space: O(N)
Example 2:
Python3
# string 1a = "rohan"# string 2b = "mohali"# store the difference of setsresult = set(a)-set(b)# print resultprint(result) |
{'r', 'n'}
Time Complexity: O(N), conversion to set takes O(n)
Auxiliary Space: O(N)
Note: The output of the above programs will always be different because sets are unordered collections, thus when subtracted they produce unordered results. By the above approach, we could obtain all the letters present in the first string but not in the second.
Example 3 :
Python3
# Program to print characters present in string1 but not in string2# string 1a = "neveropen"# string 2b = "Lazyroar"result=set()for i in a: if i not in b: result.add(i)# print resultprint(result) |
{'o', 'f', 'r'}
Time complexity: O(n), where n is the length of string1.
Auxiliary space: O(m), where m is the number of unique characters in string1 that are not in string2.
Example 4: Using operator.countOf() method
Python3
# Program to print characters present in string1 but not in string2import operator as op# string 1a = "neveropen"# string 2b = "Lazyroar"result = set()for i in a: if op.countOf(b, i) == 0: result.add(i)# print resultprint(result) |
{'f', 'o', 'r'}
Time Complexity: O(N)
Auxiliary Space : O(N)
Example 5: Using List comprehension
Python3
# string 1a = "neveropen"# string 2b = "Lazyroar"# use list comprehension to find the differenceresult = # print resultprint(result)#This code is contributed by Jyothi Pinjala. |
['f', 'o', 'r']
Time Complexity: O(N)
Auxiliary Space : O(N)
Example 6: Using filter() and lambda
Python3
a = "neveropen"b = "Lazyroar"result = set(filter(lambda x: x not in b, a))print(result)#This code is contributed by Vinay pinjala. |
{'o', 'f', 'r'}
Time Complexity: O(N)
Auxiliary Space : O(N)
Example 7: Using Recursive method.
Algorithm:
- Define a function recursive_diff() that takes two input strings string1 and string2.
- Check if the length of string1 is 0. If so, return an empty set.
- Make a recursive call to recursive_diff() with the first character of string1 removed and string2.
- If the first character of string1 is not in string2, add it to the result set obtained from the recursive call.
- Return the result set.
Python3
def recursive_diff(string1, string2): if len(string1) == 0: return set() else: result = recursive_diff(string1[1:], string2) if string1[0] not in string2: result.add(string1[0]) return result# string1a = "neveropen"# string2b = "Lazyroar"# call recursive methodresult = recursive_diff(a, b)# print resultprint(result)#this code contributed by tvsk |
{'f', 'o', 'r'}
Time complexity:
In the worst case, where all characters in string1 are not in string2, the function will perform a recursive call n times, where n is the length of string1. The time complexity of each recursive call is O(1) because it only involves checking if the first character of string1 is in string2. Therefore, the overall time complexity of the function is O(n).
Auxiliary space:
In the worst case, where all characters in string1 are not in string2, the function will perform a recursive call n times, where n is the length of string1. Each recursive call creates a new set to hold the result. Therefore, the space complexity of the function is O(n^2) because it requires n sets each with an average size of n/2 elements. However, the actual space complexity will be lower than O(n^2) because Python’s garbage collector will reclaim memory from the sets that are no longer needed.
