Mark As Completed Discussion
Home > Dynamic Programming > Dynamic Programming > Longest Common Subsequence

Introduction

Welcome to the Introduction of the Longest Common Subsequence problem!

In this lesson, we will dive into the Longest Common Subsequence problem, its significance, and applications. The Longest Common Subsequence problem is a classic problem in computer science and has various real-world applications.

The Longest Common Subsequence (LCS) problem involves finding the longest subsequence that is common to two given strings. 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. Unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences.

Why is the Longest Common Subsequence problem important? It serves as a foundation for various other problems in computer science, such as DNA sequence comparison, plagiarism detection, file diffing, and many more.

By understanding and mastering the Longest Common Subsequence problem, you'll be equipped with a powerful algorithmic technique called dynamic programming, which can be applied to solve a wide range of problems efficiently.

So let's get started and explore the world of Longest Common Subsequence!

Try this exercise. Is this statement true or false?

The Longest Common Subsequence problem involves finding the longest substring that is common to two given strings.

Press true if you believe the statement is correct, or false otherwise.

Subsequence vs Substring

When working with strings, you may come across the terms "subsequence" and "substring." Although they sound similar, they have different meanings and use cases.

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. For example, let's consider the string "algodaily". If we remove the letters "l", "g", and "y", we get the subsequence "aoday". Notice that the order of the remaining letters remains the same.

On the other hand, a substring is a contiguous sequence of characters within a string. In the same example, if we take the characters from index 3 to 5, we get the substring "day".

So, the key difference between a subsequence and a substring is that a subsequence can leave out characters and the order matters, while a substring must have contiguous characters with no gaps.

Now, let's see some code examples to understand the difference better:

SNIPPET
1string str = "algodaily";
2string subsequence = "aday";
3string substring = "dayl";
4
5bool isSubsequence = IsSubsequence(str, subsequence);
6bool isSubstring = IsSubstring(str, substring);
7
8Console.WriteLine("Is subsequence: " + isSubsequence);
9Console.WriteLine("Is substring: " + isSubstring);
10
11bool IsSubsequence(string str, string subsequence)
12{
13    int subIdx = 0;
14    for (int i = 0; i < str.Length && subIdx < subsequence.Length; i++)
15    {
16        if (str[i] == subsequence[subIdx])
17        {
18            subIdx++;
19        }
20    }
21    return subIdx == subsequence.Length;
22}
23
24bool IsSubstring(string str, string substring)
25{
26    return str.Contains(substring);
27}

In the above code snippet, we have two functions: IsSubsequence and IsSubstring. The IsSubsequence function iterates through the characters of the str and checks if each character matches the corresponding character in the subsequence. If all the characters in the subsequence are found in the str in the same order, it returns true, indicating that the subsequence is present in the str. On the other hand, the IsSubstring function simply uses the Contains method of the str to check if the substring is present.

By understanding the difference between a subsequence and a substring, you'll be able to approach different string manipulation problems effectively and choose the appropriate technique based on the problem requirements.

RUN CODERESET
CSHARP
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

Let's test your knowledge. Fill in the missing part by typing it in.

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. On the other hand, a substring is a contiguous sequence of characters within a string. The key difference between a subsequence and a substring is that a subsequence can leave out characters and the order matters, while a substring must have contiguous characters with no gaps. So, a "_" can leave out characters and the order matters, while a "substring" must have contiguous characters with no gaps.

Write the missing line below.

Recursion

Recursion is a programming technique that involves solving a problem by breaking it down into smaller subproblems. In the context of the Longest Common Subsequence problem, recursion can be used to find the length of the longest common subsequence between two strings.

Let's take a look at a recursive approach to solve the Longest Common Subsequence problem:

TEXT/X-CSHARP
1public class LongestCommonSubsequence
2{
3    public static int FindLCS(string str1, string str2)
4    {
5        return FindLCSRecursive(str1, str2, 0, 0);
6    }
7
8    private static int FindLCSRecursive(string str1, string str2, int index1, int index2)
9    {
10        if (index1 == str1.Length || index2 == str2.Length)
11        {
12            return 0;
13        }
14
15        if (str1[index1] == str2[index2])
16        {
17            return 1 + FindLCSRecursive(str1, str2, index1 + 1, index2 + 1);
18        }
19        else
20        {
21            int length1 = FindLCSRecursive(str1, str2, index1 + 1, index2);
22            int length2 = FindLCSRecursive(str1, str2, index1, index2 + 1);
23            return Math.Max(length1, length2);
24        }
25    }
26}
27
28string str1 = "AGGTAB";
29string str2 = "GXTXAYB";
30int longestCommonSubsequence = LongestCommonSubsequence.FindLCS(str1, str2);
31Console.WriteLine("Longest Common Subsequence: " + longestCommonSubsequence);

In the above code, we define a LongestCommonSubsequence class that contains a FindLCS method to find the length of the longest common subsequence between two strings. The FindLCS method calls the FindLCSRecursive method, which takes two string parameters, str1 and str2, and two integer parameters, index1 and index2, representing the current indices in str1 and str2 respectively.

If the current indices reach the end of either string, we return 0, indicating that there are no more elements to consider in the subsequence. If the characters at the current indices are equal, we increment the length by 1 and recursively call the FindLCSRecursive method with the incremented indices. If the characters are not equal, we make two recursive calls, one with the incremented index in str1 and the same index in str2, and the other with the same index in str1 and the incremented index in str2. We then return the maximum length from these two recursive calls.

Let's see how this recursive approach works for finding the longest common subsequence between the strings "AGGTAB" and "GXTXAYB":

TEXT/X-CSHARP
1string str1 = "AGGTAB";
2string str2 = "GXTXAYB";
3int longestCommonSubsequence = LongestCommonSubsequence.FindLCS(str1, str2);
4Console.WriteLine("Longest Common Subsequence: " + longestCommonSubsequence);

When we run the above code, it will output:

SNIPPET
1Longest Common Subsequence: 4

In this case, the longest common subsequence between "AGGTAB" and "GXTXAYB" is "GTAB", which has a length of 4.

Recursion is a powerful technique for solving problems, but it can be inefficient in some cases. In the next section, we will learn about dynamic programming, which can optimize the solution for the Longest Common Subsequence problem.

RUN CODERESET
CSHARP
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

Try this exercise. Is this statement true or false?

Recursion is a programming technique that involves solving a problem by breaking it down into smaller subproblems.

Press true if you believe the statement is correct, or false otherwise.

Dynamic Programming

Dynamic programming is a powerful technique used to solve optimization problems by breaking them down into smaller overlapping subproblems and solving each subproblem only once. It is an efficient way to solve problems and can significantly reduce the time complexity.

In the context of the Longest Common Subsequence problem, dynamic programming can be used to find the length of the longest common subsequence between two strings. By using a dynamic programming approach, we can avoid redundant calculations and solve the problem in a more efficient manner.

The basic idea behind dynamic programming is to store the solutions to subproblems in a table and use those solutions to solve larger subproblems. This allows us to avoid repeating calculations and quickly find the optimal solution.

Let's take a closer look at how dynamic programming can be applied to the Longest Common Subsequence problem.

Are you sure you're getting this? Is this statement true or false?

Dynamic programming is an inefficient technique used to solve optimization problems.

Press true if you believe the statement is correct, or false otherwise.

Memoization

Memoization is a technique used in dynamic programming to optimize recursive solutions by storing previously computed results and reusing them instead of recomputing the same values multiple times. By storing the results in a memoization table or cache, we can avoid redundant calculations and improve the overall runtime of the algorithm.

In the context of the Longest Common Subsequence problem, memoization can be used to optimize the recursive solution. As we discussed earlier, the recursive solution has overlapping subproblems, which leads to redundant calculations. By using memoization, we can store the results of subproblems in a table and look them up whenever needed.

Here's an example of how the memoization technique can be implemented in C#:

TEXT/X-CSHARP
1using System;
2
3class Program
4{
5    static int[, ] memo;
6
7    static int LongestCommonSubsequence(string s1, string s2, int m, int n)
8    {
9        if (m == 0 || n == 0)
10        {
11            return 0;
12        }
13
14        if (memo[m, n] != -1)
15        {
16            return memo[m, n];
17        }
18
19        if (s1[m - 1] == s2[n - 1])
20        {
21            memo[m, n] = 1 + LongestCommonSubsequence(s1, s2, m - 1, n - 1);
22        }
23        else
24        {
25            memo[m, n] = Math.Max(LongestCommonSubsequence(s1, s2, m - 1, n), LongestCommonSubsequence(s1, s2, m, n - 1));
26        }
27
28        return memo[m, n];
29    }
30
31    static void Main(string[] args)
32    {
33        string s1 = "algorithm";
34        string s2 = "program";
35
36        int m = s1.Length;
37        int n = s2.Length;
38
39        memo = new int[m + 1, n + 1];
40        for (int i = 0; i <= m; i++)
41        {
42            for (int j = 0; j <= n; j++)
43            {
44                memo[i, j] = -1;
45            }
46        }
47
48        int length = LongestCommonSubsequence(s1, s2, m, n);
49        Console.WriteLine("Length of the Longest Common Subsequence: " + length);
50    }
51}

In the above example, we define a memoization table memo to store the results of subproblems. Before making any recursive calls, we check if the result for the current subproblem already exists in the memoization table. If it does, we return the stored result. Otherwise, we compute the result and store it in the table for future use.

By using this memoization technique, we can significantly reduce the number of recursive calls and avoid redundant calculations. This leads to improved runtime and a more efficient solution.

It's important to note that memoization works well for problems with overlapping subproblems, like the Longest Common Subsequence problem. However, it may not be as effective for problems with non-overlapping subproblems.

The memoization technique is a powerful optimization technique in dynamic programming and is widely used to improve the efficiency of recursive solutions. By avoiding repeated calculations, we can solve complex problems more efficiently and optimize the overall runtime of the algorithm.

RUN CODERESET
CSHARP
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

Try this exercise. Click the correct answer from the options.

What is the purpose of using memoization in dynamic programming?

Click the option that best answers the question.

  • To reduce the space complexity
  • To improve the time complexity
  • To avoid recursive solutions
  • To eliminate overlapping subproblems

Tabulation

In dynamic programming, tabulation is a technique used to solve problems by filling a table iteratively. The table, usually a multi-dimensional array, is filled bottom-up starting from the base cases and gradually building up the solutions to larger subproblems.

When it comes to the Longest Common Subsequence problem, the tabulation technique involves using a dynamic programming table to store the lengths of the common subsequences for different prefixes of the input strings.

Let's take a look at an example of how the tabulation technique can be implemented in C#:

TEXT/X-CSHARP
1using System;
2
3class Program
4{
5    static int LongestCommonSubsequenceTabulation(string s1, string s2)
6    {
7        int m = s1.Length;
8        int n = s2.Length;
9
10        int[, ] dp = new int[m + 1, n + 1];
11
12        for (int i = 1; i <= m; i++)
13        {
14            for (int j = 1; j <= n; j++)
15            {
16                if (s1[i - 1] == s2[j - 1])
17                {
18                    dp[i, j] = 1 + dp[i - 1, j - 1];
19                }
20                else
21                {
22                    dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
23                }
24            }
25        }
26
27        return dp[m, n];
28    }
29
30    static void Main(string[] args)
31    {
32        string s1 = "AGGTAB";
33        string s2 = "GXTXAYB";
34
35        int length = LongestCommonSubsequenceTabulation(s1, s2);
36        Console.WriteLine("Length of the Longest Common Subsequence: " + length);
37    }
38}

In the above example, we create a two-dimensional array dp to store the lengths of the common subsequences. We start filling the table from the base cases (empty strings) and gradually build up the solutions to larger subproblems.

By considering all possible prefixes of the input strings, we fill the table using the following logic:

  • If the characters at the current positions in both strings are equal, the length of the common subsequence increases by 1 compared to the length of the subsequence without the current characters. Therefore, we add 1 to the diagonal element.
  • If the characters are not equal, we take the maximum length of the common subsequences without the current characters from either the previous row or the previous column.

Once we fill the entire table, the bottom-right element of the table represents the length of the longest common subsequence. In our example, the length of the longest common subsequence is 4.

The tabulation technique is a powerful approach to solve problems using dynamic programming. It provides an efficient bottom-up solution and can be used to optimize recursive algorithms by avoiding repetitive computations.

Note: The above example is written in C#, but the same logic can be implemented in other programming languages as well, with appropriate syntax changes.

RUN CODERESET
C#
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

Are you sure you're getting this? Click the correct answer from the options.

In the tabulation technique for solving the Longest Common Subsequence problem, the dynamic programming table is filled:

Click the option that best answers the question.

    Space Optimization

    In dynamic programming, one of the areas where optimization can be applied is in the space complexity of the algorithm. By carefully designing our algorithm and data structures, we can reduce the memory usage and improve the efficiency of our solution.

    When it comes to the Longest Common Subsequence problem, there are a few techniques we can employ to optimize the space usage of the tabulation solution.

    Space Optimization Techniques

    1. Using a Single Row

    One space optimization technique is to use a single row of the dynamic programming table instead of the whole table. Since we only need the information from the previous row to calculate the current row, we can keep updating the single row array and reuse it for each row. This reduces the space complexity from O(m * n) to O(n), where m is the length of the first string and n is the length of the second string.

    Here's an example of how we can implement the tabulation solution with a single row in C#:

    TEXT/X-CSHARP
    1using System;
2
3class Program
4{
5    static int LongestCommonSubsequenceTabulation(string s1, string s2)
6    {
7        int m = s1.Length;
8        int n = s2.Length;
9
10        int[] dp = new int[n + 1];
11
12        for (int i = 1; i <= m; i++)
13        {
14            int prev = 0;
15            for (int j = 1; j <= n; j++)
16            {
17                int temp = dp[j];
18
19                if (s1[i - 1] == s2[j - 1])
20                {
21                    dp[j] = 1 + prev;
22                }
23                else
24                {
25                    dp[j] = Math.Max(dp[j], dp[j - 1]);
26                }
27
28                prev = temp;
29            }
30        }
31
32        return dp[n];
33    }
34
35    static void Main(string[] args)
36    {
37        string s1 = "AGGTAB";
38        string s2 = "GXTXAYB";
39
40        int length = LongestCommonSubsequenceTabulation(s1, s2);
41        Console.WriteLine("Length of the Longest Common Subsequence: " + length);
42    }
43}

    By using a single row array dp, we can keep track of the lengths of the common subsequences while only using O(n) space.

    1. Rolling Window

    Another technique is to use a rolling window approach, where we only keep track of a fixed number of rows at a time. Instead of storing the entire table, we store only a few rows and update them as we move forward.

    This approach reduces the space complexity to O(k * n), where k is the size of the rolling window. By limiting the number of rows we store, we can significantly reduce the space usage for large input strings.

    It's important to note that the rolling window technique requires careful handling of indices and updating of rows when moving forward.

    Conclusion

    Optimizing the space usage of the tabulation solution for the Longest Common Subsequence problem can lead to more efficient and scalable solutions. By employing techniques like using a single row or a rolling window, we can reduce the space complexity and improve the performance of our algorithm.

    As a senior engineer with 10 years of programming experience, understanding space optimization techniques is crucial in order to optimize the performance of your code. By reducing the space complexity, you can improve the efficiency of your solution and make it more scalable.

    In the next section, we will explore real-world applications of the Longest Common Subsequence problem and see how it can be used to solve various problems.

    Try this exercise. Is this statement true or false?

    Using a single row array reduces the space complexity of the tabulation solution for the Longest Common Subsequence problem from O(m * n) to O(n).

    Press true if you believe the statement is correct, or false otherwise.

    Applications

    The Longest Common Subsequence problem has several real-world applications and is used in various domains, including:

    1. DNA Sequencing: In bioinformatics, DNA sequencing plays a crucial role in understanding genetic information. The Longest Common Subsequence algorithm can be used to find the similarities and differences between DNA sequences.

    2. Version Control: Version control systems like Git use the Longest Common Subsequence algorithm to determine the differences between different versions of a file. This allows users to track and merge changes made by different contributors.

    3. Text Comparison and Diff: Text editors and diff tools use the Longest Common Subsequence algorithm to compare and find the differences between two versions of a text file.

    4. Spell Checking: Spell checkers use the Longest Common Subsequence algorithm to suggest corrections for misspelled words. By finding the longest common subsequence between the misspelled word and a dictionary of words, it can suggest the most likely correct word.

    These are just a few examples of how the Longest Common Subsequence problem is applied in real-world scenarios. By understanding the algorithm and its applications, you can solve a wide range of problems efficiently.

    RUN CODERESET
    C#
    OUTPUT
    :001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

    Try this exercise. Fill in the missing part by typing it in.

    The Longest Common Subsequence problem can be used in various domains, including __ and _.

    Write the missing line below.

    Conclusion

    Thank you for joining us in this tutorial on the Longest Common Subsequence problem!

    In this tutorial, we discussed the significance and applications of the problem, different approaches to solve it, and the role of dynamic programming in optimizing the solution.

    Here are some key takeaways from this tutorial:

    1. The Longest Common Subsequence problem is to find the length of the longest subsequence that is common to two given strings.
    2. A subsequence is a sequence of characters that appears in the same relative order, but not necessarily contiguous, in both strings.
    3. Recursive approach and dynamic programming can be used to solve the Longest Common Subsequence problem.
    4. Memoization and tabulation are two techniques used to optimize the recursive and dynamic programming solutions.
    5. The Longest Common Subsequence problem has real-world applications in DNA sequencing, version control, text comparison, and spell checking.

    Now that you have a good understanding of the Longest Common Subsequence problem, you can apply this knowledge to solve similar problems in programming interviews.

    RUN CODERESET
    C#
    OUTPUT
    :001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

    Build your intuition. Is this statement true or false?

    The Longest Common Subsequence problem can be solved using only recursive approaches.

    Press true if you believe the statement is correct, or false otherwise.

    Generating complete for this lesson!

    Programming Categories

  • Basic Arrays Interview Questions
  • Binary Search Trees Interview Questions
  • Dynamic Programming Interview Questions
  • Easy Strings Interview Questions
  • Frontend Interview Questions
  • Graphs Interview Questions
  • Hard Arrays Interview Questions
  • Hard Strings Interview Questions
  • Hash Maps Interview Questions
  • Linked Lists Interview Questions
  • Medium Arrays Interview Questions
  • Queues Interview Questions
  • Recursion Interview Questions
  • Sorting Interview Questions
  • Stacks Interview Questions
  • Systems Design Interview Questions
  • Trees Interview Questions

    • Popular Lessons

  • All Courses, Lessons, and Challenges
  • Data Structures Cheat Sheet
  • Free Coding Videos
  • Bit Manipulation Interview Questions
  • Javascript Interview Questions
  • Python Interview Questions
  • Java Interview Questions
  • SQL Interview Questions
  • QA and Testing Interview Questions
  • Data Engineering Interview Questions
  • Data Science Interview Questions
  • Blockchain Interview Questions
  • Cycling Through Cycle Sort
  • Microservices Architecture
  • Object Oriented Programming Refresher
  • Introduction to Amazon IAM
  • Node.js Architecture