Removing Duplicates from a String In-Place: Techniques and Implementations

The task of removing duplicates from a string in-place is a common coding challenge that appears in various programming interviews and real-world applications. This article explores different techniques and implementations in popular programming languages, with a focus on efficiency and in-place modifications.

Overview of Duplicates in Strings

A string can contain duplicate characters where the same character might appear more than once. The goal of removing these duplicates in-place is to minimize the memory usage and space complexity. This means that we aim to modify the original string directly without requiring additional storage, which is often challenging due to the immutable nature of strings in many programming languages.

Python Implementation

Prior to making any modifications, it's important to understand that strings in Python are immutable. This means that we cannot directly modify individual characters within a string. To overcome this, we can convert the string to a list, perform the modifications, and then convert it back to a string. Here's how to achieve this using a two-pointer technique along with a set to track seen characters:

Python Code Example

The following Python function demonstrates the in-place removal of duplicates:

def remove_duplicates(s):
    # Convert the string to a list to allow in-place modifications
    char_list  list(s)
    seen  set()
    write_index  0
    for read_index in range(len(char_list)):
        char  char_list[read_index]
        if char not in seen:
            (char)
            char_list[write_index]  char
            write_index   1
    # Join the list back into a string and return
    return ''.join(char_list[:write_index])

Example Usage:

input_string  "
example_input_string
"
result  remove_duplicates(input_string)
print(result)

This implementation effectively removes duplicates while maintaining the order of the first occurrences of characters by using a set to track seen characters and a write_index to keep track of where to write the next unique character.

Java Implementation

Java supports more sophisticated data structures for handling such tasks. In this example, we make use of the LinkedHashSet data structure to ensure the order of characters is preserved during the process of removing duplicates:

Java Code Example

import ;
public class Test {
    public static void main(String[] args) {
        String s  "
example_input_string
";
        String res  removeDuplicates(s);
        (res);
    }
    static String removeDuplicates(String s) {
        LinkedHashSet h  new LinkedHashSet<>();
        for (int i  0; i 

Here, we add all characters to the set to ensure uniqueness, and then construct a new string using the elements in the set. This approach is efficient and straightforward.

General Approach for Other Languages

While the example above is in Java, the concept of using a set to track seen characters and a buffer to build the output string can be applied to most other programming languages. The key idea is to maintain a set that keeps track of unique characters and use a buffer to construct the final string without duplicates.

Go Implementation

Go also provides elegant solutions for this problem. Here's an example implementation in Go:

package main
import "fmt"
func removeDuplicates(input string) string {
    output : []rune{}
    seen : make(map[rune]struct{})
    for _, ch : range input {
        if _, ok : seen[ch]; !ok {
            seen[ch]  struct{}{}
            output  append(output, ch)
        }
    }
    return string(output)
}
func main() {
    input : "
example_input_string
"
    output : removeDuplicates(input)
    (output)
}

This Go function uses a map for faster lookup of seen characters and a slice to build the output string. This approach ensures efficient in-place removal of duplicates.

Conclusion

Removing duplicates from a string in-place is a classic problem that can be tackled using a variety of techniques and data structures. While direct in-place modifications are challenging due to the immutability of strings, using sets and other data structures can help achieve efficient and memory-efficient solutions. This article showcases implementations in Python, Java, and Go, highlighting the versatility and best practices of handling such tasks in different programming environments.