What is the Longest Common Subsequence Problem?
The Longest Common Subsequence Problem is one of the most famous problems in Dynamic Programming.
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.
A longest subsequence of string s1 and s2 is the length of the longest subsequence which is common in both the strings.
Let’s look at an example to illustrate the concept: Given two strings as input:
s1= "abdca"
s2= "cbda"
Output: 3
This shows the longest possible subsequence of s1 which is “bda.” This can be derived from sequence s1 by deleting the element ‘a’ without changing the order of the remaining elements, hence, the length of string is 3. One brute force solution is to try all possible subsequences of ‘s1’ and ‘s2’ to find the longest one.
The problem can be dealt with various approaches, the most effective of which makes use of Dynamic Programming.
Free Resources