Based on Meneses et al. (2004). A string is a list of characters such as “1differ%”. The length of the string is the number of characters in the string. The distance between two strings is the number of positions in which the two strings differ. For example, the distance between the strings “1differ%” and “1dizzzr%” is 3.

Given a set of strings of the same length, the closest string problem is to find a string of the same length that minimizes the maximum distance between the chosen string and the given list of strings. Consider the following four strings: “median,” “differ,” “length,”

and “medium,” all with 6 characters. Find a closest string to these strings. (Hint: There are many alternative solutions.)

Modeling Problems