Finding the Longest Common Subsequence (LCS): A Dynamic Programming Approach

The Longest Common Subsequence (LCS) problem involves finding the longest subsequence that is common to both strings. A subsequence is a sequence derived from another sequence by deleting some elements without changing the order of the remaining elements.

To solve this problem using dynamic programming, we can use a 2D array to store the lengths of longest common suffixes of substrings. The idea is that if the characters at the end of both strings match, then the length of LCS is one more than the LCS of the substrings without these characters.

def longest_common_subsequence(s1: str, s2: str) -> str:
    m = len(s1)
    n = len(s2)

    # Create a 2D array to store lengths of LCSs of substrings of s1[0..m-1] and s2[0..n-1]
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Build the dp array from bottom up
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # Reconstruct the LCS from the dp array
    lcs = []
    i, j = m, n
    while i > 0 and j > 0:
        if s1[i - 1] == s2[j - 1]:
            lcs.append(s1[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    return ''.join(reversed(lcs))

The time complexity of this dynamic programming approach is O(m * n), where m and n are the lengths of the two input strings. This is because we fill a matrix of size (m+1) x (n+1). The space complexity is also O(m * n) due to the storage of the dp array.