I was asked a Question where an array of Strings is given and output all groups which consists of Similar Strings. Similar strings means strings which are at one edit distance. Ex: Input: ["ABCDE", "ABCDF", "ABCGH", "AKCDH", "ABCDG"] Output: [["ABCDE", "ABCDF", "ABCDG"], ["AKCDH"], ["ABCGH"]]. Brute force approach is trivial to consider every pair and see if they are one edit distance. Interviewer keep on insisting it has optimal approach and Brute force is not the only approach. Constraint: String contains only ASCII letters and no duplicate characters. During interview I got totally freezed on this problem and cannot think apart from Brute Force and tried with storing them in Tries(but it can become a brute force type in case first character are different, means which branch to explore and might end up exploring complete tree, which is nothing but scanning the whole array for a word). Any ideas on how to optimize this.

FollowUp: What if Array Size is very large.