Understanding Longest Common Subsequence (LCS) with Dynamic Programming

📖 What is LCS?

The Longest Common Subsequence (LCS) is a classic dynamic programming problem where you're given two strings, and the goal is to find the length of the longest subsequence common to both strings.

A subsequence is a sequence that appears in the same relative order but not necessarily contiguously.

Example:

Given:

text1 = "abcde"
text2 = "ace"

The LCS is "ace" with a length of 3.

---

💡 Dynamic Programming Approach

We solve LCS using bottom-up dynamic programming by building a 2D table dp where dp[i][j] stores the length of the LCS between the suffixes text1[i:] and text2[j:].

We iterate from the end of both strings toward the beginning to ensure that when we compute dp[i][j], all the dependent subproblems (dp[i+1][j], dp[i][j+1], and dp[i+1][j+1]) are already solved.

---

✅ Final Code: LCS Length Using DP

def longestCommonSubsequence(text1, text2):
    m = len(text1)
    n = len(text2)

    # Step 1: Create a 2D table with (m+1) x (n+1), filled with 0s
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Step 2: Fill the table from bottom to top, right to left
    for i in range(m - 1, -1, -1):     
        for j in range(n - 1, -1, -1):  
            if text1[i] == text2[j]:
                dp[i][j] = 1 + dp[i + 1][j + 1]
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j + 1])

    # Step 3: The final result is in dp[0][0]
    return dp[0][0]

text1 = "abcde"
text2 = "ace"
print("LCS length:", longestCommonSubsequence(text1, text2))

---

This implementation runs in O(m × n) time and space, where m and n are the lengths of the two input strings.