LeetCode #1143 Medium

Longest Common Subsequence

Longest subsequence (order kept, gaps allowed) present in both strings text1 and text2.

dpstring

02

Intuition

💡

Compare the strings from the front, one prefix pair at a time. dp[i][j] = LCS of text1[:i] and text2[:j]. If the two current characters match, they surely end a common subsequence: 1 + the diagonal. If not, one of them is useless — drop either and take the better result. Every subproblem is a smaller prefix pair, so the table fills row by row.

03

Approach

1

Define the state

dp[i][j] = LCS length of the first i chars of text1 and first j chars of text2. dp[0][] = dp[][0] = 0 (empty prefix shares nothing).

2

The two-case transition

Match (text1[i-1]==text2[j-1]): dp[i][j] = dp[i-1][j-1] + 1. Mismatch: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) — best of skipping one char from either string.

3

Answer & backbone

dp[m][n] is the length. This exact table is the backbone of edit distance, diff tools, and many string DPs — worth knowing cold.

04

Solution & live demo

python

▶1class Solution:
▶2    def longestCommonSubsequence(self, text1, text2):
▶3        m, n = len(text1), len(text2)
▶4        dp = [[0] * (n + 1) for _ in range(m + 1)]
▶5        for i in range(1, m + 1):
▶6            for j in range(1, n + 1):
▶7                if text1[i-1] == text2[j-1]:
▶8                    dp[i][j] = dp[i-1][j-1] + 1
▶9                else:
▶10                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
▶11        return dp[m][n]

05

Edge cases

No common characters

Table stays 0 everywhere — answer 0.

One string empty

Row/column 0 base case handles it.

Identical strings

Diagonal fills 1,2,3,… — answer is the full length.

06

Complexity

Time

O(m·n)

Space

O(m·n)

Two rows suffice for O(n) space if only the length is needed.