• 1 ≤ text1.length, text2.length ≤ 1000
• Both strings consist of lowercase English letters
• Characters must keep their relative order but need not be adjacent

First get the definition exactly right, because everything downstream depends on it. A substring is a contiguous run of characters: in "abcde", "bcd" is a substring but "ace" is not. A subsequence allows gaps, as long as the surviving characters keep their original left-to-right order: "ace" is a subsequence of "abcde", and so is "abcde" itself, and so is the empty string. "aec" is not, because e comes after c in the original.

So we want the longest string that can be carved out of both inputs by deleting characters. For "abcde" and "ace", the answer is "ace" with length 3.

A tempting idea: walk both strings with a pointer each, and every time the characters match, count it and advance both; otherwise advance one of them. But which one? That single question is the whole problem, because the choice you make now determines what remains matchable later.

Try text1 = "abcde", text2 = "aed". After matching a, we compare b against e. Advance the first string and we eventually match e and then d? No — after e in text2 comes d, and in text1 after e there is nothing. So that route gives "ae", length 2. Advance the other pointer instead and we compare b against d, eventually matching d, giving "ad", also 2. Here they tie, but it is easy to build cases where one choice is strictly better, and there is no local test that reveals which. When the right move depends on the whole rest of the input, you must try both moves and compare.

The brute force version of "try everything" is genuinely awful: enumerate all 2ⁿ subsequences of the first string and test each against the second. For 1000-character strings that is beyond hopeless.

State Definition: f(i, j) is the length of the longest common subsequence of the first i characters of text1 and the first j characters of text2.

Look at the last character on each side, text1[i-1] and text2[j-1]:

Base case: if either count reaches 0, that string is empty and nothing is common — f(0, j) = f(i, 0) = 0.

We start with the full lengths: f(n, m).

def lcs(text1, text2):
    n, m = len(text1), len(text2)
    memo = {}

    def f(i, j):
        if i == 0 or j == 0: return 0
        if (i, j) in memo: return memo[(i, j)]
        if text1[i - 1] == text2[j - 1]:
            result = 1 + f(i - 1, j - 1)
        else:
            result = max(f(i - 1, j), f(i, j - 1))
        memo[(i, j)] = result
        return result

    return f(n, m)

There are n × m states, each doing constant work: O(N × M) time — a million steps for 1000-character strings, which is nothing.

Let dp[i][j] hold what f(i, j) returned, and swap each call for an array read: on a match dp[i][j] = 1 + dp[i-1][j-1], otherwise dp[i][j] = max( dp[i-1][j], dp[i][j-1] ).

Every read points at a smaller i or j, so both loops run upward from 1, and every cell is ready when needed. Row 0 and column 0 are all zeros — the base case written as data. The answer is dp[n][m]:

def lcs(text1, text2):
    n, m = len(text1), len(text2)
    dp = [[0] * (m + 1) for _ in range(n + 1)]   # row 0 and column 0 are the zero base case

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

    return dp[n][m]

Those zero row and column are not padding for convenience — they are the base case, written as data instead of an if. That trick saves a bounds check in almost every grid-shaped table you will write.

Row i reads only row i and row i-1, never anything further. So keep two:

def lcs(text1, text2):
    n, m = len(text1), len(text2)
    prev = [0] * (m + 1)                  # row i-1
    for i in range(1, n + 1):
        cur = [0] * (m + 1)
        for j in range(1, m + 1):
            if text1[i - 1] == text2[j - 1]:
                cur[j] = 1 + prev[j - 1]
            else:
                cur[j] = max(prev[j], cur[j - 1])
        prev = cur
    return prev[m]

O(M) space. Make the shorter string the inner dimension and it is O(min(N, M)).

Between the matches, a cell just carries the larger of its neighbour above or to the left. The answer is dp[5][3] = 3, the subsequence "ace".

And a case with no overlap at all, "abc" versus "def": every comparison differs, every cell copies a zero neighbour, and the answer is 0 — the empty subsequence, which is always common to any two strings.

This is the parent of a large family. The signal is: two sequences, and progress means moving forward in one or both of them. That gives a two-dimensional state (i, j) and a small menu of moves — match and take both, or drop a character from one side.

The variations only change which moves are allowed and what they cost. Some minimise a cost instead of maximising a length. Some add a third move. Some forbid the skips, so a mismatch resets to 0. The grid stays the same; only the moves change.

When you see two sequences and a question about lining them up, reach for the (i, j) grid first, then work out the moves.