[ASSIGNMENT] String Manipulation

Question

Find the longest common subsequence in two string for example
input1 : <m a n a g e r>
input2: <d a n g e r>
output : <a n g e r> which length is 5
the longest common subsequence is anger
any language is welcome least complex solution will be appreciated
A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. So a string of length n has 2^n different possible subsequences.

Answer 1

https://code.sololearn.com/csYicuIgHUq6/?ref=app

Answer 2

1)manager naagr
//output must be "aagr" or "nagr" or both of these
2)aaab baaa
//output must be aaa
3)pool loop
//output must be oo
4)bdrcve , bcvde
//output must be bcve

https://code.sololearn.com/c88Qgivl7e6V/?ref=app

Answer 3

Here's my try...☺️
https://code.sololearn.com/cVYZNT6AQe2W/?ref=app

Answer 4

one liner in python :
https://code.sololearn.com/c5avhgertlu1/?ref=app

Answer 5

It feels great when you can solve problems in newly learnt language
https://code.sololearn.com/cpXUc3KIGp0K/?ref=app

Answer 6

thanks @Asmaa I'm just a beginner so know only two languages but will try to learn more 😊😊 good luck to you too for your dreams

Answer 7

@swim , U can see the comments on code of Yerucham
//a long discussion is present there , U will understand the challenge easily

Answer 8

Congratulations for your quiz creation master badge 👍😉

Answer 9

@ GAWEN STEASY, you are welcome 👍😉
and if you like this comment, i am going to delete both 😊

Answer 10

Hello, everyone! Here is my python code for this challenge.
Please leave your comment and upvote!

https://code.sololearn.com/c7QNrM3iJt4M/

Answer 11

//here's my try:

https://code.sololearn.com/WdBmmWv0yi79/?ref=app

Answer 12

My try
https://code.sololearn.com/cPkulBkh3792/?ref=app
Correct Solution, finally!
https://code.sololearn.com/cCuFI8b07sBP/?ref=app

Answer 13

The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from the longest common substring problem: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences. The longest common subsequence problem is a classic computer science problem, the basis of data comparison programs such as the diff utility, and has applications in bioinformatics. It is also widely used by revision control systemssuch as Git for reconciling multiple changes made to a revision-controlled collection of files.
https://en.m.wikipedia.org/wiki/Longest_common_subsequence_problem
I made this best to understand to all what is lcs problem when the challenge is over I will mark a best answer to that code

Answer 14

Here is my try:
(taking into consideration contiguous subsequence)

https://code.sololearn.com/cDQIvyPz9lJl/?ref=app

Answer 15

brute forcing always works..😉😀.. printing all if multiple subsequence with same length
https://code.sololearn.com/cremhZN2Iw7G/?ref=app

Answer 16

thanks @tooselfish😊😊

Answer 17

@Swim you are on discord then I will able to give you a perfect answer because it follows an algorithm of matrix by which the longest common subsequence is find

Answer 18

#edited
If it is truly finding comman substrings, it should not allow another characters between subsequent members of substring...Then for "manager" and "danger" output should be "ger" only...some other examples try with your codes..
1) "loop" and "pool" -->"oo"
2)"ahopebhope" and "chopedhope" -->hope
3)"pqrs" and "srqp" --> no subsequence is matching
following code is giving the same outputs if matching substring length is more then 1
https://code.sololearn.com/cBOpN9UlvlUb/?ref=app

Answer 19

These types of challenges are fun. It helps me alot.

Answer 20

@Debasish
yes it can handel multiple match, but the challenge is to get the longest so no need for other matching that's why i don't include multiple matching.
thank you for your notice.