LeetCode Solution 1143 - Longest Common Subsequence

Problem Statement

Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

A common subsequence of two strings is a subsequence that is common to both strings. If there is no common subsequence, return 0.

Constraints:

• 1 <= text1.length, text2.length <= 1000
• text1 and text2 consist only of lowercase English characters.

Optimal Approach - Dynamic Programming (Bottom-Up)

The best way to solve this problem efficiently is using Dynamic Programming (DP) with a bottom-up approach.

Explanation:

1. Create a dp table of size (m+1) x (n+1) where m and n are the lengths of text1 and text2.
2. Fill the table such that:
   • If text1[i-1] == text2[j-1], then dp[i][j] = dp[i-1][j-1] + 1.
   • Otherwise, dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
3. Return dp[m][n] as the result.

C++ Code (LeetCode-Compatible)

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        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 (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];
    }
};

Step-by-Step Explanation

1. Initialization:
   • We create a dp table of size (m+1) x (n+1) initialized to 0.
2. Filling the DP Table:
   • If characters match, take diagonal value +1.
   • Otherwise, take the maximum from the top or left cell.
3. Return the Last Cell:
   • dp[m][n] contains the length of the longest common subsequence.

Dry Run / Execution Steps

Example:

Input: text1 = "abcde", text2 = "ace"

DP Table Calculation:

     a c e
   0 0 0 0
 a 0 1 1 1
 b 0 1 1 1
 c 0 1 2 2
 d 0 1 2 2
 e 0 1 2 3

Output: 3

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force (Recursion)	Exponential $O(2^n)$	O(n)	Very slow for large inputs
Top-Down DP (Memoization)	O(m*n)	O(m*n)	Similar efficiency but requires recursion overhead
Bottom-Up DP (Iterative)	O(m*n)	O(m*n)	Best for performance and readability
Space-Optimized DP	O(m*n)	O(n)	Reduces memory usage but harder to understand

Best Solution & Why It’s Best

The bottom-up DP approach is the most efficient because:

1. It avoids recursion overhead.
2. It has a predictable time complexity of O(m*n).
3. It guarantees the optimal solution.

Complexity Analysis

• Time Complexity: O(m * n) (where m and n are lengths of text1 and text2)
• Space Complexity: O(m * n) (can be optimized to O(n)).

Conclusion

• The best approach is Bottom-Up Dynamic Programming.
• Alternative approaches like recursion or memoization fail in efficiency.
• Recommended practice problems:
  • Edit Distance (LeetCode 72)
  • Distinct Subsequences (LeetCode 115)
  • Shortest Common Supersequence (LeetCode 1092)