Leetcode 1143. Longest Common Subsequence

Problem

The given problem is to find the longest common subsequence between two strings text1 and text2. A subsequence is a string that is derived from the original string by deleting some (may be none) characters without changing the order of the remaining characters. For example "ace" is a subsequence of "abcde". A common subsequence of two strings is a subsequence which is common in both strings.

If there are no common subsequences, we return 0.

For example:

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

In this problem, the length of both strings will be between 1 and 1000 and will only consists of lowercase English characters.

Approach

The problem can be solved using the concept of dynamic programming. The basic idea is to generate a 2D array dp where dp[i][j] represents the length of the longest common subsequence of text1[0..i) and text2[0..j).

We begin by iterating over each character of the two strings. If the characters at the current indices of the two strings are equal, we increment the length of the longest common subsequence found till now which will be stored at dp[i][j] i.e. one element diagonally above the current element. On the other hand, if the characters are not equal, we take the maximum of dp[i][j + 1] and dp[i + 1][j] which represent the length of the longest common subsequence found by excluding the current character from either of the two strings.

Finally, dp[m][n] will give us the length of the longest common subsequence of the two input strings where m and n are the lengths of the two input strings.

Java Solution

1
2java
3class Solution {
4    public int longestCommonSubsequence(String text1, String text2) {
5        int m = text1.length();
6        int n = text2.length();
7        int[][] dp = new int[m + 1][n + 1];
8
9        for (int i = 0; i < m; i++) {
10            for (int j = 0; j < n; j++) {
11                if (text1.charAt(i) == text2.charAt(j)) {
12                    dp[i + 1][j + 1] = 1 + dp[i][j];
13                } else {
14                    dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
15                }
16            }
17        }
18
19        return dp[m][n];
20    }
21}

Python Solution

1
2python
3class Solution:
4    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
5        m, n = len(text1), len(text2)
6        dp = [[0]*(n+1) for _ in range(m+1)]
7
8        for i in range(m):
9            for j in range(n):
10                if text1[i] == text2[j]:
11                    dp[i+1][j+1] = dp[i][j] + 1
12                else:
13                    dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
14
15        return dp[-1][-1]

Javascript Solution

1
2javascript
3var longestCommonSubsequence = function(text1, text2) {
4    const m = text1.length, n = text2.length;
5    const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));
6
7    for (let i = 0; i < m; i++) {
8        for (let j = 0; j < n; j++) {
9            if (text1[i] === text2[j]) {
10                dp[i + 1][j + 1] = 1 + dp[i][j];
11            } else {
12                dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
13            }
14        }
15    }
16    return dp[m][n];
17};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int longestCommonSubsequence(string text1, string text2) {
6        int m = text1.size(), n = text2.size();
7        vector<vector<int>> dp(m+1,vector<int> (n+1,0));
8        for(int i = 0; i < m; i++) {
9            for(int j = 0; j < n; j++) {
10                if(text1[i] == text2[j])
11                    dp[i+1][j+1] = dp[i][j] + 1;
12                else
13                    dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
14            }
15        }
16        return dp[m][n];
17    }
18};

C# Solution

1
2csharp
3public class Solution {
4    public int LongestCommonSubsequence(string text1, string text2) {
5        int m = text1.Length, n = text2.Length;
6        int[,] dp = new int[m+1, n+1];
7        
8        for (int i = 0; i < m; i++) {
9            for (int j = 0; j < n; j++) {
10                if (text1[i] == text2[j]) {
11                    dp[i+1, j+1] = 1 + dp[i, j];
12                } else {
13                    dp[i+1, j+1] = Math.Max(dp[i, j+1], dp[i+1, j]);
14                }
15            }
16        }
17        return dp[m, n];
18    }
19}

Ruby Solution

1
2ruby
3def longest_common_subsequence(text1, text2)
4  m, n = text1.length, text2.length
5  dp = Array.new(m+1) {Array.new(n+1, 0)}
6  
7  for i in 0...m
8    for j in 0...n
9      if text1[i] == text2[j]
10        dp[i+1][j+1] = dp[i][j] + 1
11      else
12        dp[i+1][j+1] = [dp[i][j+1], dp[i+1][j]].max
13      end
14    end
15  end
16  return dp[-1][-1]
17end

PHP Solution

1
2php
3function longestCommonSubsequence($text1, $text2) {
4  $m = strlen($text1);
5  $n = strlen($text2);
6  $dp = array_fill(0, $m+1, array_fill(0, $n+1, 0));
7
8  for ($i = 0; $i < $m; $i++) {
9    for ($j = 0; $j < $n; $j++) {
10      if ($text1[$i] == $text2[$j]) {
11        $dp[$i+1][$j+1] = 1 + $dp[$i][$j];
12      } else {
13        $dp[$i+1][$j+1] = max($dp[$i][$j+1], $dp[$i+1][$j]);
14      }
15    }
16  }
17  return $dp[$m][$n];
18}

In conclusion, the longest common subsequence problem is a classic dynamic programming problem that can be solved with a straightforward tabulation approach. We benefit from the overlapping subproblems and optimal substructure properties of the problem and build a table to store our subproblem solutions. By iterating over the characters of both strings, the text1 and text2, we can fill up our table and ultimately find the length of their longest common subsequence in the last cell of our table. The concept is essentially the same across all programmed languages. The syntax may vary between languages, but the underlying principles remain consistent. Furthermore, the concept of dynamic programming remains one of the most fundamental aspects of computer science, and it is utilized in a wide range of problems beyond just longest common subsequence.