Write Python code to remove duplicates from a string.

The most Pythonic and efficient way to remove duplicate characters from a string while preserving their original order is by leveraging dict.fromkeys() or an explicit ordered set-like approach. Both achieve O(N) time complexity.

Mechanics and Why

Python's dict.fromkeys(iterable) method creates a new dictionary where elements from the iterable become keys. Since dictionary keys must be unique, this naturally deduplicates the characters. Crucially, from Python 3.7+, dictionaries preserve insertion order, making dict.fromkeys() a concise and elegant solution. Converting this dictionary back to a string using ''.join() reconstructs the deduplicated string.

Alternatively, for explicit control or compatibility with older Python versions (pre-3.7), an ordered set-like approach can be used. This involves iterating through the string, adding each character to a set (for O(1) average-case lookup) if it hasn't been seen, and appending it to a list. This ensures both uniqueness and order preservation.

Example and Trade-offs

The dict.fromkeys() method is concise and highly readable. Its time complexity is O(N) because each character is processed once, and dictionary key insertion/lookup is O(1) on average. Space complexity is also O(N) in the worst case (all unique characters).

def dedupe_str(s: str) -> str:
    """Removes duplicate characters from a string, preserving order."""
    return ''.join(dict.fromkeys(s))

For extremely large strings, a generator expression with a set (e.g., seen=set(); ''.join(c for c in s if c not in seen and not seen.add(c))) can be slightly more memory-efficient. This avoids creating an intermediate list or dictionary of the full string's characters before joining, processing characters one by one. This is analogous to how data engineers use generators or iterators to process large datasets without loading everything into memory, similar to processing records in a Kafka topic or rows in a Spark RDD.

In the interview, also mention…

Discuss the importance of order preservation (a common requirement for string deduplication), and how character sets (e.g., Unicode vs. ASCII) don't affect the core logic but might impact memory if characters are multi-byte. Also, consider edge cases like empty strings or strings with only unique characters.