Longest Common Subsequence

Let's solve the Longest Common Subsequence problem using Dynamic Programming.

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.

Let’s say you have the following two strings:

  • “cloud”
  • “found”

The longest common subsequence between these two strings is “oud”, which has a length of 33.

Constraints:

  • 1<=1 <= str1.length <=500<= 500
  • 1<=1 <= str2.length <=500<= 500
  • str1 and str2 contain only lowercase English characters.

Examples

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.