We are given a string and we need to remove all duplicates from it? What will be the output if the order of character matters? Examples:
Input : neveropen
Output : geksfor
This problem has an existing solution please refer to Remove all duplicates from a given string.
Method 1:
Python3
from collections import OrderedDict# Function to remove all duplicates from string# and order does not matterdef removeDupWithoutOrder(str): # set() --> A Set is an unordered collection # data type that is iterable, mutable, # and has no duplicate elements. # "".join() --> It joins two adjacent elements in # iterable with any symbol defined in # "" ( double quotes ) and returns a # single string return "".join(set(str))# Function to remove all duplicates from string# and keep the order of characters samedef removeDupWithOrder(str): return "".join(OrderedDict.fromkeys(str))# Driver programif __name__ == "__main__": str = "neveropen" print ("Without Order = ",removeDupWithoutOrder(str)) print ("With Order = ",removeDupWithOrder(str)) |
Without Order = foskerg With Order = geksfor
Time complexity: O(n)
Auxiliary Space: O(n)
Method 2:
Python3
def removeDuplicate(str): s=set(str) s="".join(s) print("Without Order:",s) t="" for i in str: if(i in t): pass else: t=t+i print("With Order:",t) str="neveropen"removeDuplicate(str) |
Without Order: kogerfs With Order: g With Order: ge With Order: ge With Order: gek With Order: geks With Order: geksf With Order: geksfo With Order: geksfor With Order: geksfor With Order: geksfor With Order: geksfor With Order: geksfor With Order: geksfor
Time complexity: O(n)
Auxiliary Space: O(n)
What do OrderedDict and fromkeys() do?
An OrderedDict is a dictionary that remembers the order of the keys that were inserted first. If a new entry overwrites an existing entry, the original insertion position is left unchanged.
For example, see below code snippet :
Python3
from collections import OrderedDictordinary_dictionary = {}ordinary_dictionary['a'] = 1ordinary_dictionary['b'] = 2ordinary_dictionary['c'] = 3ordinary_dictionary['d'] = 4ordinary_dictionary['e'] = 5# Output = {'a': 1, 'c': 3, 'b': 2, 'e': 5, 'd': 4}print (ordinary_dictionary) ordered_dictionary = OrderedDict()ordered_dictionary['a'] = 1ordered_dictionary['b'] = 2ordered_dictionary['c'] = 3ordered_dictionary['d'] = 4ordered_dictionary['e'] = 5# Output = {'a':1,'b':2,'c':3,'d':4,'e':5}print (ordered_dictionary) |
{'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5}
OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)])
Time complexity: O(n)
Auxiliary Space: O(1)
fromkeys() creates a new dictionary with keys from seq and values set to a value and returns a list of keys, fromkeys(seq[, value]) is the syntax for fromkeys() method. Parameters :
- seq : This is the list of values that would be used for dictionary keys preparation.
- value : This is optional, if provided then the value would be set to this value.
For example, see below code snippet :
Python3
from collections import OrderedDictseq = ('name', 'age', 'gender')dict = OrderedDict.fromkeys(seq)# Output = {'age': None, 'name': None, 'gender': None}print (str(dict))dict = OrderedDict.fromkeys(seq, 10)# Output = {'age': 10, 'name': 10, 'gender': 10}print (str(dict)) |
OrderedDict([('name', None), ('age', None), ('gender', None)])
OrderedDict([('name', 10), ('age', 10), ('gender', 10)])
Time complexity: O(n)
Auxiliary Space: O(1)
This article is contributed by Shashank Mishra (Gullu). If you like Lazyroar and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the Lazyroar main page and help other Geeks.
Method 5: using operator.countOf() method
Python3
import operator as opdef removeDuplicate(str): s = set(str) s = "".join(s) print("Without Order:", s) t = "" for i in str: if op.countOf(t, i) > 0: pass else: t = t+i print("With Order:", t)str = "neveropen"removeDuplicate(str) |
Without Order: goksefr With Order: g With Order: ge With Order: ge With Order: gek With Order: geks With Order: geksf With Order: geksfo With Order: geksfor With Order: geksfor With Order: geksfor With Order: geksfor With Order: geksfor With Order: geksfor
Time Complexity: O(N)
Auxiliary Space : O(N)
