Program to Remove All Duplicates 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 languages 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 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 For Loop
• Python List

Python Code

msg = " ababacd"
li = [0] * 26
print(msg)
out= ""
for ch in msg:
    ind = ord(ch) - ord('a')
    if li[ind] == 0:
       out=out+ch
       li[ind] = 1

print(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 the 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.