Longest Common Subsequence - Leetcode Solution

Problem:

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. (eg, "ace" is a subsequence of "abcde" while "aec" is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

Example 1:

Input: text1 = "abcde", text2 = "ace" Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "def" Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Solution:

This problem can be solved using dynamic programming. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. We can solve this problem by using two strings. We can then compare the characters of the two strings and find the maximum length of a common subsequence.

We can use a dynamic programming matrix dp[i][j] to store the length of the longest common subsequence of the first i characters of text1 and the first j characters of text2.

dp[i][j] will be the length of the LCS of the two substrings ending at position i and j respectively.

dp[i][j] can be calculated as dp[i][j-1] if the current character of text2 is not in the LCS, or dp[i][j-1] + 1 if it is.

Similarly, dp[i][j] can be calculated as dp[i-1][j] if the current character of text1 is not in the LCS, or dp[i-1][j] + 1 if it is.

The final answer will be the value of dp[n][m], where n is the length of text1 and m is the length of text2.

Code:

int longestCommonSubsequence(string text1, string text2) { int n = text1.length(), m = text2.length(); int dp[n+1][m+1]; for(int i=0;i<=n;i++) dp[i][0] = 0; for(int j=0;j<=m;j++) dp[0][j] = 0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;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[n][m]; }

The time complexity of the solution is O(nm), where n and m are the lengths of the input strings. The space complexity of the solution is O(nm).

1