Longest Common Subsequence
Explore how to determine the longest common subsequence between two strings using dynamic programming techniques in C++. Understand subsequence concepts, constraints, and apply your skills in coding exercises to solve this classic optimization problem.
We'll cover the following...
Statement
Suppose you are given two strings. You need to find the length of the longest common subsequence between these two strings.
A subsequence is a string formed by removing some characters from the original string while maintaining the relative position of the remaining characters. For example, “abd” is a subsequence of “abcd”, where the removed character is “c”.
If there is no common subsequence, then return 0.
Constraints:
-
str1.length -
str2.length str1andstr2contain only lowercase English characters.
Examples
Understand the problem
Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:
What is the output if the following two strings are given as inputs?
str1 = “educative”, str2 = “education”
Figure it out!
We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.
Try it yourself
Implement your solution in the following coding playground.
int LongestCommonSubsequence(const std::string& str1, const std::string& str2) {// Replace this placeholder return statement with your codereturn -1;}