algo-longest-common-subseq

Answer

The longest common subsequence (LCS) problem is solved with classic DP:

1. DP Table: Build an (m+1)×(n+1) table dp where dp[i][j] = length of LCS of s1[:i] and s2[:j]. If characters match, take dp[i-1][j-1] + 1; otherwise take max(dp[i-1][j], dp[i][j-1]).

2. Backtracking: Walk backwards from dp[m][n]. When chars match, include the char and move diagonally (i-1, j-1). Otherwise move in the direction of the larger DP value. Reverse the collected characters at the end.

Here's the core implementation:

def longest_common_subsequence(s1: str, s2: str):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    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])

    # Backtrack
    lcs_chars = []
    i, j = m, n
    while i > 0 and j > 0:
        if s1[i - 1] == s2[j - 1]:
            lcs_chars.append(s1[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    return dp[m][n], ''.join(reversed(lcs_chars))

Unicode handling: Python str is Unicode-native. Indexing and comparison work correctly for CJK characters, emoji, accented letters, and any other Unicode code points. No extra encoding/decoding is needed.