Longest Common Subsequence (Dynamic Programming)

		A	E	D	F	H	R

How Longest Common Subsequence Works

The Longest Common Subsequence (LCS) problem is to find the longest subsequence present in both the given sequences. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.

The algorithm:

Create a table to store LCS lengths for all subproblems
Fill the table using bottom-up dynamic programming
The value in the bottom-right cell is the length of the LCS
Backtrack through the table to construct the LCS

This dynamic programming approach solves the problem in O(mn) time complexity, where m and n are the lengths of the input strings.

function LCS(X, Y):
    m = length of X
    n = length of Y
    L = 2D array of size (m+1) x (n+1)
    
    for i from 0 to m:
        for j from 0 to n:
            if i == 0 or j == 0:
                L[i][j] = 0
            elif X[i-1] == Y[j-1]:
                L[i][j] = L[i-1][j-1] + 1
            else:
                L[i][j] = max(L[i-1][j], L[i][j-1])
            visualize(L, i, j, X, Y)
    
    return L[m][n]

function visualize(L, i, j, X, Y):
    // Update UI to show:
    // 1. The current state of the L array
    // 2. Highlight the current cell being calculated
    // 3. Show the comparison between X[i-1] and Y[j-1]
    // 4. Indicate which case of the algorithm is being applied