A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For example, 'abd' is a subsequence of 'abcd' whereas 'adc' is not Given 2 strings containing lowercase english alphabets, find the length of the Longest Common Subsequence L.C.S.. Example: Input:  'abcdgh' 'aedfhr' Output: 3 Explanation: The longest subsequence common to both the string is adh Time Complexity : OMN Space Complexity : OMN, where M and N are the lengths of the 1st and 2nd string respectively. :param s1: string :param s2: string :return: int matij : contains length of LCS of s10..i1 and s20..j1
def longest_common_subsequence(s_1, s_2):
    """
    :param s1: string
    :param s2: string
    :return: int
    """
    m = len(s_1)
    n = len(s_2)

    mat = [[0] * (n + 1) for i in range(m + 1)]
    # mat[i][j] : contains length of LCS of s_1[0..i-1] and s_2[0..j-1]

    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 or j == 0:
                mat[i][j] = 0
            elif s_1[i - 1] == s_2[j - 1]:
                mat[i][j] = mat[i - 1][j - 1] + 1
            else:
                mat[i][j] = max(mat[i - 1][j], mat[i][j - 1])

    return mat[m][n]
