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.

--

--

--

Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Knowledge Sharing: Category-based Interpretation of Kubernetes v1.14 Release Notes

MySQL — Ongoing Replication using Data Migration Service from AWS

The easiest way to install Ubuntu on an encrypted partition

REST Api using Spring Boot

How to build a dapp on Tezos?

Why I change to use Golang?

SQL- lingua franca for data analysis

Reverse engineering CityBee’s API for fun and not profit

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Placewit

Placewit

Upskilling students for tech placements!

More from Medium

Scattered Rice Coding Question

55. Jump Game

Interview preparation -DSA #day1

Most Commonly Asked DSA Question in Interview — 2022