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

Mirror String

Haskell Book: Chapter 22: Reader

Getting Started with Git

Code that debugs itself: Fixing a deadlock with a watchdog

Running External Commands in Deno

A Voting DAPP on PARASTATE TestNet

OpenLampTech issue #10

The Cloud Dilemma: How Enterprise Companies Should Navigate The Transition To The Cloud

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

Class Quiz

Graph Algorithms

Monotonic Stack Problems

Priority Queues and Dijkstra’s Algorithm