Removing duplicates in a string in Python

Question

What is an efficient algorithm to removing all duplicates in a string?

For example : aaaabbbccdbdbcd

Required result: abcd

Answer 1

You use a hashtable to store currently discovered keys (access O(1)) and then loop through the array. If a character is in the hashtable, discard it. If it isn't add it to the hashtable and a result string.

Overall: O(n) time (and space).

The naive solution is to search for the character is the result string as you process each one. That O(n²).