Given two strings s1 and s2 return the length of the longest common subsequence of characters between the two strings.

longest_common_subsequence.py

"""
Input:
s1 = "ADC"
s2 = "ABCD"

Output: 2
Explanation:
"ADC"
"ABCD"
Both strings share the subsequence "A", "D".
"""

class Solution:
    def longestCommonSubsequenceLength(self, s1, s2):
        '''Using bottom-up optimized DP solution.
        :type s1: str
        :type s2: str
        :rtype: int
        '''
        s2_ln = len(s2)
        cache = [0 for _ in range(s2_ln + 1)]

        # row
        for s1_idx, s1_char in enumerate(s1):
            # set last as 0 for matrix {r,c} = {"", ""}
            prev = 0
            # col
            for s2_idx, s2_char in enumerate(s2):
                temp = cache[s2_idx + 1]
                if s1_char == s2_char:
                    cache[s2_idx + 1] = 1 + prev
                else:
                    cache[s2_idx + 1] = max(
                            cache[s2_idx + 1],  # from last know matrix array
                            cache[s2_idx],  # latest updated
                        )
                prev = temp
        return cache[-1]