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

Elasticsearch — Search in your local language

A List with the Best Trading Journal Software Solutions.

Set up MathWallet for BurgerSwap | Tutorials

My First Blog

Android rich text: Overview

Swarm architecture — a view from above

“It’s Only A Model”

Comparable in Java

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

One Mile on the globe Puzzle

Interview Question 2— All Possible Solutions

LeetCode 238 — Product of Array Except Self

Path With Minimum Effort