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();
            var added = "";
            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
                        cluster.Add(distance, new List<Tuple<string, string>>());

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

                    cluster[distance].Add(new Tuple<string, string>(item, item2));

                    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;

                            computed.Add(longest);
                        }

                        var currentAdded = computed.OrderBy(s => s.Length).FirstOrDefault();
                        var diff = string.IsNullOrEmpty(added) || string.IsNullOrEmpty(currentAdded)
                            ? string.Empty
                            : currentAdded.Replace(added, string.Empty);

                        if (!string.IsNullOrEmpty(currentAdded) && diff.Length == currentAdded.Length)
                        {
                            var ff = computed2.OrderBy(s => s.Length).FirstOrDefault();
                            if (ff.Length >= minimumStringLength)
                                clusterGroups.Add(ff);

                            computed2.Clear(); // TODO: check false
                            computed2.Add(diff);
                        }
                        else
                        {
                            if (diff.Length == 0 && !string.IsNullOrEmpty(added) && !string.IsNullOrEmpty(currentAdded))
                                computed2.Add(diff);
                        }

                        added = currentAdded;
                        cluster.Clear();
                        first = item;
                    }

                    ++k;
                }

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

            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.