# Get shortest grouped (distinct) string from Hashset of strings

Well, I just have a lot of strings that have common parts between them and not all of them. By this reason, I wanted to group them by their longest common part and take from that the minimum from each list of groups. So I have this code:

namespace Program
{
public static class Utils
{
public static string LongestCommonSubstring(this IEnumerable<string> arr)
{
// Determine size of the array
var n = arr.Count();

// Take first word from array as reference
var s = arr.ElementAt(0);
var len = s.Length;

var res = "";

for (var i = 0; i < len; i++)
{
for (var j = i + 1; j <= len; j++)
{
// generating all possible substrings
// of our reference string arr[0] i.e s
var stem = s.Substring(i, j - i);
var k = 1;
//for (k = 1; k < n; k++) {
foreach (var item in arr.Skip(1))
{
// Check if the generated stem is
// common to all words
if (!item.Contains(stem))
break;

++k;
}

// If current substring is present in
// all strings and its length is greater
// than current result
if (k == n && res.Length < stem.Length)
res = stem;
}
}

return res;
}

public static HashSet<string> GetShortestGroupedString(this HashSet<string> items, int distanceThreshold = 3, int minimumStringLength = 2)
{
var cluster = new Dictionary<int, List<Tuple<string, string>>>();
var clusterGroups = new HashSet<string>();

var itemCount = items.Count * items.Count;
int k = 0;

var first = items.First();
foreach (var item in items)
//Parallel.ForEach(merged, item => // TODO
{
var computed2 = new List<string>();
foreach (var item2 in items)
{
var distance = LevenshteinDistance.Compute(item, item2);
var firstDistance = LevenshteinDistance.Compute(first, item2);

if (!cluster.ContainsKey(distance)) // TODO: check false

if (distance > distanceThreshold)
{
++k;
continue;
}

if (firstDistance > distance)
{
var computed = new List<string>();
foreach (var kv in cluster)
{
if (kv.Value.Count == 0) continue;
var longest = kv.Value.Select(dd => dd.Item1).LongestCommonSubstring();
if (string.IsNullOrEmpty(longest)) continue;

}

var currentAdded = computed.OrderBy(s => s.Length).FirstOrDefault();
? string.Empty

{
var ff = computed2.OrderBy(s => s.Length).FirstOrDefault();
if (ff.Length >= minimumStringLength)

computed2.Clear(); // TODO: check false
}
else
{
}

cluster.Clear();
first = item;
}

++k;
}

var f = computed2.OrderBy(s => s.Length).FirstOrDefault();
if (f.Length >= minimumStringLength)
}
//});

return clusterGroups;
}
}

/// <summary>
/// Contains approximate string matching
/// </summary>
internal static class LevenshteinDistance
{
/// <summary>
/// Compute the distance between two strings.
/// </summary>
public static int Compute(string s, string t)
{
var n = s.Length;
var m = t.Length;
var d = new int[n + 1, m + 1];

// Step 1
if (n == 0)
{
return m;
}

if (m == 0)
{
return n;
}

// Step 2
for (var i = 0; i <= n; d[i, 0] = i++)
{
}

for (var j = 0; j <= m; d[0, j] = j++)
{
}

// Step 3
for (var i = 1; i <= n; i++)
{
//Step 4
for (var j = 1; j <= m; j++)
{
// Step 5
var cost = (t[j - 1] == s[i - 1]) ? 0 : 1;

// Step 6
d[i, j] = Math.Min(
Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
d[i - 1, j - 1] + cost);
}
}
// Step 7
return d[n, m];
}
}
}


The LevenshteinDistance class was extracted from: https://stackoverflow.com/a/2344347/3286975

The LongestCommonString method was extracted from: https://www.geeksforgeeks.org/longest-common-substring-array-strings/

Then, I just want to ensure if there is any optimization for it.

I already tried Parallel.ForEach option but the order of execution is important here.

• It would be nice to see how do you test it and measure the performance. Spoiler: there's lots of possible optimizations. Dec 28 '21 at 23:31