Longest Common Subsequence-Asked in VMware
Problem Statement :
Given two sequences, find the length of the longest subsequence present in both of them. Both the strings are of uppercase.
The first and the second line of the input contains the length of the two sequences.
The third and fourth line of the input contains the two subsequences
You have to output the length of the largest subsequence (not necessarily contiguous) between them.
Explanation of given Test Cases :
Longest Common Subsequence for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.
There are 2 states for this DP. String 1 and String 2, as any combination of characters of these strings can form subsequence, hence we need to iterate every character of string 2 for every character of string 1
Therefore, a 2D DP array will be formed.
- A character may or may not be included in the subsequence. There are 2 cases:
If characters of string1 and string2 match, then it may be a part of the subsequence.
If not, then 2 more cases arise:
a) Either the matching character appears in string1 before the position of this character
b) Or, matching character appears in string2 before the position of character
if character match then DP[i][j] = DP[i-1][j-1] + 1
else DP[i][j] = max(DP[i-1][j], DP[i][j-1])
3. Iterate for complete DP array
4. Return DP[m][n] (m, n — size of strings)