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 param s1 string param s2 string return int mat i j contains length of lcs of s_1 0 i 1 and s_2 0 j 1
def longest_common_subsequence(s_1, s_2):
    
    m = len(s_1)
    n = len(s_2)

    mat = [[0] * (n + 1) for i in range(m + 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]