DEV Community

Alkesh Ghorpade
Alkesh Ghorpade

Posted on • Originally published at alkeshghorpade.me

LeetCode - Longest Common Subsequence

Problem statement

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

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.

  • For example, 'ace' is a subsequence of 'abcde'.

A common subsequence of two strings is a subsequence that is common to both strings.

Problem statement taken from: https://leetcode.com/problems/longest-common-subsequence

Example 1:

Input: text1 = 'abcde', text2 = 'ace'
Output: 3
Explanation: The longest common subsequence is 'ace' and its length is 3.
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: text1 = 'abc', text2 = 'abc'
Output: 3
Explanation: The longest common subsequence is 'abc' and its length is 3.
Enter fullscreen mode Exit fullscreen mode

Example 3:

Input: text1 = 'abc', text2 = 'def'
Output: 0
Explanation: There is no such common subsequence, so the result is 0.
Enter fullscreen mode Exit fullscreen mode

Constraints:

- 1 <= text1.length, text2.length <= 1000
- text1 and text2 consist of only lowercase English characters.
Enter fullscreen mode Exit fullscreen mode

Explanation

Recursion

A naive solution is to check every subsequence of text1[1..n] to see if it is also a subsequence of text2[1..m]. To achieve this, we can break down the problem into smaller subproblems until the solution becomes trivial. We shorten each sequence by removing the last element to break the problem into subproblems. We recursively perform the same operation on the shortened string and keep pulling the last part until we reach the string's first character.

Removing the last character of the strings depends on two situations.

  • text1 and text2 both end in the same element
LCS(text1[1..n], text2[1..m]) = LCS(text1[1..n - 1], text2[1..m - 1]) if text1[n] == text2[m]
Enter fullscreen mode Exit fullscreen mode
  • text1 and text2 do not end in the same element

Let's take an example to understand this.

text1 = 'abc'
text2 = 'abcde'
Enter fullscreen mode Exit fullscreen mode

text1 ends with c, while text2 ends with e. We can remove the last character e from the string text2 and reduce our problem to LCS(text1[1..n], text2[1..m - 1])

Similarly, we remove the last character c from string text1 and reduce our problem to LCS(text1[1..n - 1], text2[1..m]). We want to compute the length of the longest common subsequence. We handle this case using the below approach.

LCS(text1[1..n], text2[1..m]) = max(LCS(text1[1..n], text2[1..m - 1]), LCS(text1[1..n - 1], text2[1..m]))
Enter fullscreen mode Exit fullscreen mode

A C++ snippet of the above approach is as below:

int lcsLength(string text1, string text2, int n, int m) {
    if(n == 0 || m == 0) {
        return 0;
    }

    if(text1[n - 1] == text2[m - 1]) {
        return lcsLength(text1, text2, n - 1, m - 1) + 1;
    }

    return max(lcsLength(X, Y, m, n - 1), lcsLength(X, Y, m - 1, n));
}
Enter fullscreen mode Exit fullscreen mode

The time complexity of the above approach is O(2 ^(n + m)) and space complexity is O(1).

Dynamic programming

The above approach has overlapping subproblems. Let's construct a partial recursion tree for the above example to verify the overlapping subproblems.

text1 = 'abc'
text2 = 'abcde'

n = text1.length
  = 3

m = text2.length
  = 5

                        (3, 5)
                   ________|_________
                  |                  |
                (2, 5)             (3, 4)
                  |                  |
     _____________|                  |_____________
     |            |                  |             |
    (1, 5)      (2, 4)              (2, 4)        (3, 3)

    (2, 4) is computed twice.
Enter fullscreen mode Exit fullscreen mode

The subproblem (2, 4) is computed twice. We know that problems having optimal substructure and overlapping subproblems can be solved by dynamic programming.

Let's check the algorithm first.

- set n = text1.size()
      m = text2.size()

- initialize 2D array int dp[n + 1][m + 1]

- loop for i = 1; i <= n; i++
    loop for j = 1; j <= m; j++
      if text1[i - 1] == text2[j - 1]
        - update dp[i][j] = dp[i - 1][j - 1] + 1
      else
        - update dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])

- return dp[n][m]
Enter fullscreen mode Exit fullscreen mode

The time complexity of the above approach is O(N * M) and the space complexity is O(N * M).

Let's check our algorithm in C++, Golang, and Javascript.

C++ solution

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

        return dp[n][m];
    }
};
Enter fullscreen mode Exit fullscreen mode

Golang solution

func longestCommonSubsequence(text1 string, text2 string) int {
    n := len(text1)
    m := len(text2)
    dp := make([][]int, n + 1)

    for i := range dp {
        dp[i] = make([]int, m + 1)
    }

    for i := 1; i <= n; i++ {
        for 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][j - 1], dp[i - 1][j])
            }
        }
    }

    return dp[n][m]
}

func max(a, b int) int {
    if a > b {
        return a
    }

    return b
}
Enter fullscreen mode Exit fullscreen mode

Javascript solution

var longestCommonSubsequence = function(text1, text2) {
    let n = text1.length;
    let m = text2.length;
    let dp = new Array(n + 1).fill(0);

    for (let i = 0; i < n + 1; i++) {
        dp[i] = new Array(m + 1).fill(0);
    }

    for(let i = 1; i <= n; i++) {
        for(let 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] = Math.max(dp[i- 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[n][m];
};
Enter fullscreen mode Exit fullscreen mode

Let's dry-run our algorithm for Example 1.

Input: text1 = 'abcde'
       text2 = 'ace'

Step 1: n = text1.size()
          = 5
        m = text2.size()
          = 3

Step 2: dp(n + 1, vector<int>(m + 1, 0))
        dp = [
               [0, 0, 0, 0],
               [0, 0, 0, 0],
               [0, 0, 0, 0],
               [0, 0, 0, 0],
               [0, 0, 0, 0],
               [0, 0, 0, 0]
             ]

Step 3: loop for i = 1; i <= n
          1 <= 5
          true

          loop for j = 1; j <= m
            1 <= 3
            true

            if text1[i - 1] == text2[j - 1]
               text1[0] == text2[0]
               'a' == 'a'
               true

               dp[i][j] = dp[i - 1][j - 1] + 1
               dp[1][1] = dp[0][0] + 1
                        = 1

            j++
            j = 2

          loop for j <= m
            2 <= 3
            true

            if text1[i - 1] == text2[j - 1]
               text1[0] == text2[1]
               'a' == 'c'
               false

            else
               dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
               dp[1][2] = max(dp[1][1], dp[0][2])
                        = max(1, 0)
                        = 1

            j++
            j = 3

          loop for j <= m
            3 <= 3
            true

            if text1[i - 1] == text2[j - 1]
               text1[0] == text2[2]
               'a' == 'e'
               false

            else
               dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
               dp[1][3] = max(dp[1][2], dp[0][3])
                        = max(1, 0)
                        = 1

            j++
            j = 4

          loop for j <= m
            4 <= 3
            false

          i++
          i = 2

          dp = [
               [0, 0, 0, 0],
               [0, 1, 1, 1],
               [0, 0, 0, 0],
               [0, 0, 0, 0],
               [0, 0, 0, 0],
               [0, 0, 0, 0]
             ]

Step 4: loop for i = 1; i <= n
          2 <= 5
          true

          loop for j = 1; j <= m
            1 <= 3
            true

            if text1[i - 1] == text2[j - 1]
               text1[1] == text2[0]
               'b' == 'a'
               false

            else
               dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
               dp[2][1] = max(dp[2][0], dp[1][1])
                        = max(0, 1)
                        = 1

            j++
            j = 2

          loop for j = 1; j <= m
            2 <= 3
            true

            if text1[i - 1] == text2[j - 1]
               text1[1] == text2[1]
               'b' == 'c'
               false

            else
               dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
               dp[2][2] = max(dp[2][1], dp[1][2])
                        = max(1, 1)
                        = 1

            j++
            j = 3

          loop for j = 1; j <= m
            3 <= 3
            true

            if text1[i - 1] == text2[j - 1]
               text1[1] == text2[2]
               'b' == 'e'
               false

            else
               dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
               dp[2][3] = max(dp[2][2], dp[1][3])
                        = max(1, 1)
                        = 1

            j++
            j = 4

            loop for j <= m
              4 <= 3
              false

          i++
          i = 3

          dp = [
               [0, 0, 0, 0],
               [0, 1, 1, 1],
               [0, 1, 1, 1],
               [0, 0, 0, 0],
               [0, 0, 0, 0],
               [0, 0, 0, 0]
             ]

Step 5: loop for i = 1; i <= n
          3 <= 5
          true

          loop for j = 1; j <= m
            1 <= 3
            true

            if text1[i - 1] == text2[j - 1]
               text1[3] == text2[0]
               'c' == 'a'
               false

            else
               dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
               dp[3][1] = max(dp[3][0], dp[2][1])
                        = max(0, 1)
                        = 1

            j++
            j = 2

            loop for j = 1; j <= m
              2 <= 3
              true

              if text1[i - 1] == text2[j - 1]
                 text1[2] == text2[1]
                 'c' == 'c'
                 true

                 dp[i][j] = dp[i - 1][j - 1] + 1
                 dp[3][2] = dp[2][1] + 1
                          = 1 + 1
                          = 2

              j++
              j = 3

            loop for j = 1; j <= m
              3 <= 3
              true

              if text1[i - 1] == text2[j - 1]
                 text1[2] == text2[2]
                 'c' == 'e'
                 false

              else
                 dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
                 dp[3][3] = max(dp[3][2], dp[2][3])
                          = max(2, 1)
                          = 2

              j++
              j = 4

              loop for j <= m
                4 <= 3
                false

            i++
            i = 4

            dp = [
               [0, 0, 0, 0],
               [0, 1, 1, 1],
               [0, 1, 1, 1],
               [0, 1, 2, 2],
               [0, 0, 0, 0],
               [0, 0, 0, 0]
            ]

Step 6: loop for i = 1; i <= n
          4 <= 5
          true

          loop for j = 1; j <= m
            1 <= 3
            true

            if text1[i - 1] == text2[j - 1]
               text1[3] == text2[0]
               'd' == 'a'
               false

            else
               dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
               dp[4][1] = max(dp[4][0], dp[3][1])
                        = max(0, 1)
                        = 1

            j++
            j = 2

          loop for j = 1; j <= m
            2 <= 3
            true

            if text1[i - 1] == text2[j - 1]
               text1[3] == text2[1]
               'd' == 'c'
               false

            else
               dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
               dp[4][2] = max(dp[4][1], dp[3][2])
                        = max(1, 2)
                        = 2

            j++
            j = 3

          loop for j = 1; j <= m
            3 <= 3
            true

            if text1[i - 1] == text2[j - 1]
               text1[3] == text2[2]
               'd' == 'e'
               false

            else
               dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
               dp[4][3] = max(dp[4][2], dp[3][3])
                        = max(2, 2)
                        = 2

            j++
            j = 4

            loop for j <= m
              4 <= 3
              false

          i++
          i = 5

          dp = [
               [0, 0, 0, 0],
               [0, 1, 1, 1],
               [0, 1, 1, 1],
               [0, 1, 2, 2],
               [0, 1, 2, 2],
               [0, 0, 0, 0]
             ]

Step 7: loop for i = 1; i <= n
          5 <= 5
          true

          loop for j = 1; j <= m
            1 <= 3
            true

            if text1[i - 1] == text2[j - 1]
               text1[4] == text2[0]
               'e' == 'a'
               false

            else
               dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
               dp[5][1] = max(dp[5][0], dp[4][1])
                        = max(0, 1)
                        = 1

            j++
            j = 2

            loop for j = 1; j <= m
              2 <= 3
              true

              if text1[i - 1] == text2[j - 1]
                 text1[4] == text2[1]
                 'e' == 'c'
                 false

              else
                 dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
                 dp[5][2] = max(dp[5][1], dp[4][2])
                        = max(1, 2)
                        = 2

              j++
              j = 3

            loop for j = 1; j <= m
              3 <= 3
              true

              if text1[i - 1] == text2[j - 1]
                 text1[4] == text2[3]
                 'e' == 'e'
                 true

                 dp[i][j] = dp[i - 1][j - 1] + 1
                 dp[5][3] = dp[4][2] + 1
                          = 2 + 1
                          = 3

              j++
              j = 4

              loop for j <= m
                4 <= 3
                false

            i++
            i = 6

            dp = [
               [0, 0, 0, 0],
               [0, 1, 1, 1],
               [0, 1, 1, 1],
               [0, 1, 2, 2],
               [0, 1, 2, 2],
               [0, 1, 2, 3]
            ]

Step 8: loop for i = 1; i <= n
          6 <= 5
          false

Step 9: return dp[n][m]
               dp[5][3] = 3

We return the answer as 3.
Enter fullscreen mode Exit fullscreen mode

Top comments (0)