Program to Remove All Duplicates Chars from a given String in Python
Problem Statement:
You have given a string. You need to remove all the duplicates from the string.
The final output string should contain each character only once. The respective order of the characters inside the string should remain the same.
You can only traverse the string at once.
Example:
Input string: ababacd
Output string: abcd
You can use any programming language like C/C++, Java, Python, or anything you are comfortable with…
Remove all Duplicates from a given String in Python
In Python, we can use the set() method, to remove all the duplicate characters. But it will not preserver the ordering of the character.
print("".join(set("ababacd")))Output:
acbd
Note: Every time you run this code, you will get a different output. The set operation returns characters in different orders.
Our output should be abcd.
Here is the solution.
Algorithm:
- Create the list of size 26. Initialize all the elements in the list to zero. (This is nothing but the array/list of 26 flags. The first element in the list will be for the character ‘a’, the second element in the list will be for character ‘b’ and so on…).
- Initialize the output string as an empty string.
- Loop over all the characters in the given string from right to left.
- Check the flag value for the given character.
- If the flag is False (0), the given character is occurring the first time. Append that character to the output string. Set the flag to True (1).
- If the flag is True (1), don’t do anything.
Prerequisite:
Python Code
msg = " ababacd"
li = [0] * 26
print(f"Origional string: {msg}")
out= ""
for ch in msg:
ind = ord(ch) - ord('a')
if li[ind] == 0:
out=out+ch
li[ind] = 1
print(f"Unique characters in string: {out}") Output:
abcd
Complexity:
You are traversing all the characters in the string only once, it takes linear time i.e. O(n) where ‘n’ is the length of the string.
It takes extra space to store the flag for all 26 characters. It will be always the same size despite the length of the string. The space complexity will be O(1).
What’s next?
This is the simple program to remove all duplicates from a given string in Python.
What are the other solutions you can provide to solve this problem? You can share your solutions in any programming language.
Comments
Suvidh Jain
It can be done in this way to.
from collections import OrderedDict string = input("") a = list(OrderedDict.fromkeys(string)) b = ''.join(a) print(b)Aniruddha Chaudhari
Looks good.
MOHIT .
>>> from collections import Counter
>>> “”.join(list(Counter(‘ababacd’)))
‘abcd’
Aniruddha Chaudhari
Interesting!
Manoj Kumar
we could have done this
msg="abcdabedcd" print(" ".join(sorted(set(msg))))Saswata
This is the best one.
Klex
expanding on MOHIT’s method; the list is reduntant
>>> from collections import Counter
>>> “”.join(Counter(‘ababacd’))
‘abcd’
Dassen
Here is my solution. May it helps.
a = 'ababacd' b = [] for i in a: if i not in b: b.append(i) print("".join(b))Alister
Nice answer bro.
Sahil Kumar Vishwakarma
Elegent yet simple.
Aniruddha Chaudhari
This solution is simple but it involves time complexity for membership operation. When you are writing it in interview or competitive programming, they expect optimized code in terms of complexity.