You asked a How do I question. You probably asked a Should I question. As in "Should I release a data set that reveals the distance between two strings where everything else is anonymized?" The answer is No unless you're making a crossword puzzle. (XKCD beat me to the joke for something similar. Your scenario is much more crossword-like however.)
Even if you found a scheme that didn't directly reveal individual letters, just having the information you get from string edit distances reveals a lot of information. Example: You have two records in a medical trial program with similar demographic data. You suspect "Bob Example Sr." and "Bob Example Jr." participated. Your two similar rows of data have “ “ “anonymized” ” ” (this needs triple scare quotes to triple scare you out of becoming responsible for publicizing poorly anonymized data) name records which are both 15 characters long and differ in one character. Start making guesses.
One could also build a weighted graph of dictionary words. (Where every node is a word and every pair of nodes is connected by an edge with weight equal to their edit distance.) For your idea you are hiding the labels of each node but not the edges or weights. One could make an informed guess at the values of the encrypted data by looking for similar sub-graphs in both the encrypted and dictionary-based graphs. Once you find one answer it becomes easier to guess the rest.
It is very difficult to design a system that anonymizes complex data sets. Otherwise intelligent people think they're outwitting hackers when they do things like hash email address, credit card info, or social security numbers. And that's the most obviously de-anonymizable scheme one can think of.
The most powerful tool to deanonymize data is to exploit the relations between data. If the purpose of your encryption is anonymization while maintaining properties in the original data then you're trying to do two things that are at odds with each other. It's a lot like deliberately encrypting with the same key/nonce pair even if you could find the perfect scheme.
Now to answer the "How do I [best stick a fork in an electrical socket"] part. I can think of three methods.
- Store a table that relates pairs of records to their edit distance. This requires $O(n^2)$ space but is the least bad option. Omit the original string data or substitute it with randomly assigned ID numbers. You can't add new data to an annoymized database with this method.
- If you want the Hamming distance between two strings, then use one substitution cipher for the first character of each string, another for the second, and so on. Breaking a substitution cipher is easy enough that it requires no knowledge of modern cryptography. (Or much knowledge at all beyond literacy.)
- If you want Levenshtein distance then you use only one substitution cipher. This choice is also horribly insecure.
There may be better privacy-preserving methods than 2 and 3, but not 1. There may be way more complicated ways involving "multi-party secure distance computation, oblivious transform such as secure modular hashing, additive homomorphic encryption" but if any scheme leaks the data you say you want to preserve to a person who holds a copy of the supposedly anonymized data then it's no better at preserving privacy than 1.