Official 1940 views

Editorial: Longest Common Subsequence

by admin · Oct. 18, 2026

1 Intuition

dp[i][j] = LCS of the first i chars of text1 and first j chars of text2.

2 Approach

If the current characters match, extend the diagonal; otherwise take the better of dropping one character from either string. Keep only one row.

3 Complexity Analysis

Time O(n·m), Space O(m).

4 Solution Code

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        prev = [0] * (len(text2) + 1)
        for a in text1:
            cur = [0]
            for j, b in enumerate(text2):
                cur.append(prev[j] + 1 if a == b else max(prev[j + 1], cur[j]))
            prev = cur
        return prev[-1]

5 Code Walkthrough

The reference solution below implements the approach step by step.