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.

Input Format

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

Output Format:

You have to output the length of the largest subsequence (not necessarily contiguous) between them.

Given:

6
6
ABCDGH
AEDFHR

Output:

3

Explanation of given Test Cases :

Longest Common Subsequence for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.

Approach:

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.

Now,

1. 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

2. Therefore,
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)

Code:

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.