Pass Double Optimal Wunsch Needleman .. aka PDOWN algorithm - optimal string given variations

Optimal.cs

string[] LP = new string[] {
    "DH869*",
    "DHB69",
    "DH69",
    //"DH869",
    "H689",
    "DH89"
};

// Produces "DH869" - based on the LP data
Console.WriteLine($"Optimal License: {PDOWN(LP)}");

string PDOWN(string[] variatons)
{
    char[]? NeedlemanWunsch(char[] x, char[] y)
    {
        int[,] scores = new int[x.Length + 1, y.Length + 1];
        int i = 0;
        int j = 0;
        for (i = 0; i <= x.Length; i++) scores[i, 0] = i;
        for (j = 0; j <= y.Length; j++) scores[0, j] = j;
        for (i = 1; i <= x.Length; i++)
        {
            for (j = 1; j <= y.Length; j++)
            {
                int match = (x[i - 1] == y[j - 1]) ? 0 : 1;
                int insert = scores[i, j - 1] + 1;
                int delete = scores[i - 1, j] + 1;
                int substitute = scores[i - 1, j - 1] + match;
                scores[i, j] = Math.Min(Math.Min(insert, delete), substitute);
            }
        }
        i = x.Length;
        j = y.Length;
        List<char> alignmentX = new List<char>();
        List<char> alignmentY = new List<char>();
        while ((i > 0) || (j > 0))
        {
            if ((i > 0) && (scores[i, j] == scores[i - 1, j] + 1))
            {
                alignmentX.Add(x[i - 1]);
                alignmentY.Add('*');
                i--;
            }
            else if ((j > 0) && (scores[i, j] == scores[i, j - 1] + 1))
            {
                alignmentX.Add('*');
                alignmentY.Add(y[j - 1]);
                j--;
            }
            else
            {
                alignmentX.Add(x[i - 1]);
                alignmentY.Add(y[j - 1]);
                i--;
                j--;
            }
        }
        alignmentX.Reverse();
        alignmentY.Reverse();
        return alignmentY.ToArray();
    }
    string[] Align(string[] al)
    {
        List<string> LPAligned = new List<string>();
        for (int i = 0; i < LP.Length; i++)
        {
            var x = LP[i];
            for (int j = 0; j < LP.Length; j++)
            {
                if (i == j) continue;
                var y = LP[j];
                var aligned = NeedlemanWunsch(x.ToArray(), y.ToArray());
                LPAligned.Add(new string(aligned));
            }
        }
        return LPAligned.ToArray();
    }
    var LPAligned = Align(LP);
    LPAligned = Align(LP);
    var size = LPAligned.Max(g => g.Length);
    for (int i = 0; i < LPAligned.Length; i++)
    {
        int m = LPAligned[i].Length;
        if (m < size)
        {
            var a = Enumerable.Range(0, size - m).Select(x => '*').ToArray();
            LPAligned[i] = $"{LPAligned[i]}{new string(a)}";
        }
    }
    string final = "";
    for (int i = 0; i < size; i++)
    {
        var e = LPAligned.SelectMany(x => new string(new char[] { x[i] })).GroupBy(x => x).OrderByDescending(x => x.Count()).First().Key;
        final += e;
    }

    final = final.Replace("*", "");
    return final;
}