Eliminate Duplicate Characters in a String

This question requires you to create an algorithm that takes a string as input and produces a new string with all duplicate characters eliminated. The efficiency of the algorithm is crucial, as repeatedly iterating over each character can become excessively time-consuming for larger strings. Make sure to ask your interviewer whether the output string should preserve the original character order, and also confirm if the algorithm needs to be case sensitive. To tackle this problem effectively, think about utilizing a data structure such as a hash set or a dictionary, which enables constant time complexity for both search and insertion operations.

Here’s a Python solution that utilizes a dictionary to track characters that have already been encountered. def remove_duplicates ( input_string ) : seen = { } output_string = '' for character in input_string : if character not in seen : output_string += character seen [ character ] = True return output_string This code loops through the input string and for each character, checks if it exists in the seen dictionary. If it does not, the character is added to output_string and marked as seen. If it is already present in seen , the loop proceeds to the next character. Ultimately, output_string will consist of the original characters without any duplicates.

Let's explore an alternative method using Python. In this example, we utilize list mutation alongside a conditional statement to filter out duplicates while maintaining the original sequence of characters. def remove_duplicates ( input_string ) : output_string = [ ] [ output_string . append ( i ) for i in input_string if not output_string . count ( i ) ] return '' . join ( output_string ) For each character in the input string, we verify whether that character is already in output_string . If it isn't, we add it to the end. Finally, we concatenate the list of characters into a string before returning it. This method also retains the original character order. However, it may be less efficient since the count operation within the list comprehension operates in linear time, resulting in an overall time complexity of O(n^2).