class Solution:
    '''
    Time Complexity: O(m * n)
    Space Complexity: O(m * n)
    Where, m is length of text1, n is length of text2.
    There is also a space optimized solution with O(min(m, n)) space complexity, 
    but this is good enough for interview.
    '''
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        @cache
        def dp(i, j):
            if i >= len(text1) or j >= len(text2):
                return 0
            if text1[i] == text2[j]:
                return 1 + dp(i+1,j+1)
            else:
                return max(dp(i, j+1), dp(i+1, j))
        return dp(0,0)