1. If text1[i] equals text2[j], we assume this character is part of the LCS and add 1 to the result of solve(i+1, j+1).
2. If they do not match, we branch into two possibilities:
   • Skip the current character of text1 and calculate solve(i+1, j).
   • Skip the current character of text2 and calculate solve(i, j+1).
   • Take the maximum of these two results.

Pseudo-code:

text
function solve(i, j):
    if i == length(text1) or j == length(text2):
        return 0
    if text1[i] == text2[j]:
        return 1 + solve(i + 1, j + 1)
    else:
        return max(solve(i + 1, j), solve(i, j + 1))

Time Complexity Analysis: The time complexity is $O(2^{\max(M, N)})$, where $M$ and $N$ are the lengths of the strings. In the worst case (e.g., no matching characters), the recursion tree branches twice at every step, leading to exponential growth.

Why it fails: For string lengths up to 1000 (as per the constraints), $2^{1000}$ is astronomically large. This approach essentially re-solves the same subproblems (e.g., solve(5, 5)) millions of times, leading to a Time Limit Exceeded (TLE) error.

Core Insight for Longest Common Subsequence

The key intuition is that the decision at any pair of indices (i, j) depends entirely on the results of the immediate previous states. We can construct the solution bottom-up (or top-down with memoization) by filling a 2D grid where dp[i][j] represents the LCS of the prefix text1[0...i-1] and text2[0...j-1].

The transition logic relies on a specific invariant:

1. Match Case: If the characters text1[i] and text2[j] match, they must contribute to the LCS. We extend the LCS found for the prefixes ending before i and j. Geometrically, this looks like taking the value from the top-left diagonal cell and adding 1.
2. Mismatch Case: If the characters do not match, the LCS length is essentially "carried over" from the best result obtained so far. We cannot use both current characters simultaneously to extend a match. Therefore, the value is the maximum of the cell directly above (excluding current char of text1) or the cell directly to the left (excluding current char of text2).

Visual Description: Imagine a grid where rows represent characters of text1 and columns represent characters of text2. We fill this grid row by row. When we are at cell (i, j), we look at three neighbors: top, left, and top-left.

• If the row/column characters match, the value flows from the top-left neighbor plus one.
• If they don't match, the value is the larger of the top or left neighbor. This effectively propagates the "best score found so far" through the grid.

Algorithm Strategy: DP - 2D Array (Longest Common Subsequence - LCS)

1. State Definition: Create a 2D array dp of size (m + 1) x (n + 1), where m and n are the lengths of text1 and text2. dp[i][j] stores the length of the Longest Common Subsequence between the first i characters of text1 and the first j characters of text2.

2. Initialization: Initialize the first row and first column with 0. This represents the base case: the LCS of any string and an empty string is 0. This padding simplifies index management.

3. Iteration: Iterate through the grid using nested loops: i from 1 to m, and j from 1 to n.

4. State Transition: Inside the loop, compare text1[i-1] and text2[j-1] (adjusting for 0-based indexing of strings vs 1-based indexing of DP table).

   • If text1[i-1] == text2[j-1]: dp[i][j] = 1 + dp[i-1][j-1]
   • If text1[i-1] != text2[j-1]: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

5. Result: The value at dp[m][n] contains the length of the LCS for the complete strings.

Execution Flow

Let's trace text1 = "ace", text2 = "abcde". DP Table size: 4 x 6. Initialized with 0s.

1. i=1 ('a'), j=1 ('a'):
   • 'a' == 'a'.
   • dp[1][1] = 1 + dp[0][0] = 1.
2. i=1 ('a'), j=2 ('b'):
   • 'a' != 'b'.
   • dp[1][2] = max(dp[0][2], dp[1][1]) = max(0, 1) = 1.
   • (Logic: We carry over the match 'a' found previously).
3. ... skipping to i=2 ('c'), j=3 ('c'):
   • 'c' == 'c'.
   • dp[2][3] = 1 + dp[1][2].
   • dp[1][2] was 1 (from the 'a' match). So dp[2][3] = 2.
4. ... skipping to i=3 ('e'), j=5 ('e'):
   • 'e' == 'e'.
   • dp[3][5] = 1 + dp[2][4].
   • dp[2][4] carried over the value 2. So dp[3][5] = 3.

Final result at dp[3][5] is 3 ("ace").

Proof of Correctness

The correctness relies on the principle of optimality. For any two prefixes S1 and S2:

1. If the last characters match (x == y), then the LCS must include this character. The problem reduces to finding the LCS of S1 without x and S2 without y. If we didn't include x, we would be wasting a matching pair, which contradicts the goal of finding the longest subsequence.
2. If the last characters do not match (x != y), the LCS cannot end with a match at this exact position. The LCS must be formed either by ignoring x (solution lies in LCS(S1-x, S2)) or ignoring y (solution lies in LCS(S1, S2-y)). Since we want the maximum length, taking the max of these two subproblems covers all valid possibilities. By induction, since the base cases (empty strings) are correct, and every step makes a locally optimal choice based on correct sub-results, the final result is globally optimal.

Reference Implementation

C++ Solution for LeetCode 1143

cpp
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.length();
        int n = text2.length();
        
        // dp[i][j] stores the LCS length of text1[0...i-1] and text2[0...j-1]
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                // If characters match, extend the diagonal result
                if (text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } 
                // If mismatch, carry over the max from top or left
                else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        return dp[m][n];
    }
};

Java Solution for LeetCode 1143

java
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        
        // dp[i][j] represents the LCS of text1.substring(0, i) and text2.substring(0, j)
        int[][] dp = new int[m + 1][n + 1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // Check characters (adjust for 0-based indexing)
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        return dp[m][n];
    }
}

Python Solution for LeetCode 1143

python
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        
        # Initialize (m+1) x (n+1) grid with zeros
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                # Compare characters corresponding to current dp index
                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[m][n]