LeetCode 1143 - Longest Common Subsequence

Given two strings text1 and text2, this Medium dynamic programming problem asks for the length of their longest common subsequence (LCS). I used a bottom-up 2D DP table where each state represents the LCS length between prefixes of the two strings.

---

Problem link and explanation

• Problem: 1143. Longest Common Subsequence
• Summary: Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

Unlike a substring, a subsequence does not require contiguous characters, but the relative order of elements must be preserved. For example, the LCS of "abcde" and "ace" is "ace", yielding a length of 3.

---

Approach

Define dp[i][j] as the LCS length between prefix text1[0...i-1] and prefix text2[0...j-1]. The table dimensions are (m + 1) x (n + 1) with all entries initialized to 0 to account for empty prefix bases.

m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]

for i in range(1, m + 1):
    for j in range(1, n + 1):
        if text1[i - 1] == text2[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

1. Matching characters (text1[i-1] == text2[j-1]): The current character extends the optimal subsequence found without either character, so take the diagonal value and add 1 (dp[i-1][j-1] + 1).
2. Mismatched characters (text1[i-1] != text2[j-1]): The optimal solution must omit one of the two characters, so take the maximum of the adjacent states (max(dp[i-1][j], dp[i][j-1])).

The final entry dp[m][n] holds the LCS length for the full strings.

---

Complexity analysis

• Time complexity: O(m × n)
  • Fills an (m + 1) × (n + 1) table where each cell computation takes constant time.
• Space complexity: O(m × n)
  • Allocates a 2D array of size (m + 1) × (n + 1).

---

Implementation code

class Solution:

    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

        return dp[m][n]

---

Summary and reflection

The recurrence relation for longest common subsequence cleanly divides into two discrete cases based on character equality. Recognizing that character matches depend on the diagonal predecessor while mismatches propagate the maximum from the top or left cells forms the foundation for many 2D sequence alignment algorithms.