using System;

public class Program

{

    public static void Main()

    {

        // Test Case #1

        string s1 = "HARRY";

        string s2 = "SALLY";

        Console.WriteLine(commonChild(s1,s2)); // 2

        // Test Case #2

        string s3 = "AA";

        string s4 = "BB";

        Console.WriteLine(commonChild(s3,s4)); // 0

        // Test Case #3

        string s5 = "SHINCHAN";

        string s6 = "NOHARAAA";

        Console.WriteLine(commonChild(s5,s6)); // 3

        // Test Case #4

        string s7 = "OUDFRMYMAW";

        string s8 = "AWHYFCCMQX";

        Console.WriteLine(commonChild(s7,s8)); // 2

    }

    // Complete the commonChild function below.

    /*

     *

     * A string is said to be a child of a another string if it can be formed by deleting 0 or more characters from the other string. 

     * Given two strings of equal length, what's the longest string that can be constructed such that it is a child of both?

     *

     * For example, ABCD and ABDC have two children with maximum length 3, ABC and ABD. 

     * They can be formed by eliminating either the D or C from both strings. 

     * Note that we will not consider ABCD as a common child because we can't rearrange characters and ABCD  ABDC.

     *

     * https://gist.github.com/riyadparvez/5924851

     * https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

     *

     */

    static int commonChild(string s1, string s2) {

​

        int [,] arr = new int [s1.Length+1, s2.Length+1];

        for(int i = 0; i <= s2.Length; i++)

        {

            arr[0, i] = 0;

        }

        for (int i = 0; i <= s1.Length; i++)

        {   

            arr[i, 0] = 0;

        }

        for (int i = 1; i <= s1.Length; i++)

        {

            for (int j = 1; j <= s2.Length; j++)

            {

                if (s1[i-1] == s2[j-1])

                {

                    arr[i, j] = arr[i - 1, j - 1] + 1;

                }

                else

                {

                    arr[i, j] = Max(arr[i-1, j], arr[i, j-1]);

                }

            }

        }

        return arr[s1.Length, s2.Length];

    }

    private static int Max(int int1, int int2)

    {

        return int1 > int2 ? int1 : int2;

    }

}