Turkmenistan is 8 edits, United States is 9. Levenshtein Distance is not actually a good search algorithm :)

That's correct, yes. Turkmenistan: 8 deletions (Trkmesan). United States: 9 deletions (ed States), including the space character.

You'll have to add more weights to substring matches, fuzzy search by itself is usually not enough for intuitive search