1143. Longest Common Subsequence

📝 Problem Details

• Title: 1143. Longest Common Subsequence
• Link: https://leetcode.com/problems/longest-common-subsequence/
• Difficulty: Medium
• Tags/Categories: Dynamic-Programming

input strings text1 and text2 return the length of their longest common subsequence return 0 if there is no common subsequence subsequence: new string generated from the original string with some or no characters deleted without changing the relative order of the remaining characters

💭What Were My Initial Thoughts?

1. Can it be broken into subproblems?
	- if the last characters of both strings match, they contribute to the LCS
	- otherwise, we must consider the LCS by ignoring either the last character of `text1` or `text2`.

2. Choose Top-Down vs Bottom-Up
	- can use either
	- will go with a bottom up approach where we buld the solution from smaller substrings

3. Define DP State
	- let dp[i][j] represent the length of the LCS for 
	- `text1[0..i-1]` and `text2[0..j-1]
	- base case: if either string is empty, LCS is 0 
		- dp[0][j] = 0
		- dp[i][0] = 0

💡 Explanation of Solution

---

1. Base Case: Building the Foundation

• imagine we are filling out a grid (DP table) where:

  • rows represent text1 (first string)
  • columns represent text2 (second string)
  • each cell dp[i][j] represents the LCS length for text1[0...i-1] and text2[0...j-1].**

• Why do we set the entire first row and column to zero?

  • if either string is empty, there is no common subsequence, so the LCS is 0
  • this is why we initialize:
    • dp[0][j] = 0 → When text1 is empty.
    • dp[i][0] = 0 → When text2 is empty.

This gives us the following starting DP table for text1 = "abcde" and text2 = "ace":

   ''  a  c  e
''  0  0  0  0
a   0
b   0
c   0
d   0
e   0

Each 0 in the first row and first column means “no characters” in one of the strings, so LCS is 0.

2. Filling the Table - How do we move?

• Case 1: Characters match
  • text1[i-1] == text2[j-1]
  • if they match, they contribute to the LCS
  • we extend the LCS from the previous diagonal cell dp[i-1][j-1] and add 1
  • Formula: dp[i][j] = 1 + dp[i-1][j-1]

• Case 2: Characters don’t match
  • text1[i-1] != text2[j-1]
  • we must ignore one character from either text1 or text2 and take the maximum LCS possible from previous results
  • Formula: dp[i][j] = max(dp[i-1][j], dp[i][j-1]

Final Answer

at the end of filling the table, dp[m][n] contains the length of the longest common subsequence

   ''  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  <-- Final answer = `dp[5][3] = 3`

⌛ Complexity Analysis

Time Complexity: O(m * n)
Space Complexity: O(m * n)

💻 Implementation of Solution

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size();
        int n = text2.size();
 
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
 
        // fill dp table bottom up
        for(int i=1; i <= m; i++) {
            for(int j=1; j <= n; j++) {
                if (text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = 1 + dp[i - 1][j - 1]; // Match, extend LCS
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); // Exclude one character
                }
            }
        }
        return dp[m][n];
    }
};