+68

Challenge: String Manipulation

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.

2/8/2018 1:13:50 PM

GAWEN STEASY

55 Answers

New Answer

+43

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

+35

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

+32

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

+24

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

+19

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

+17

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

+16

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

+14

Hello, everyone! Here is my python code for this challenge. Please leave your comment and upvote! https://code.sololearn.com/c7QNrM3iJt4M/

+13

Can someone clarify how is longest common subsequence in the challange example <m a n a g e r> and <d a n g e r> is <a n g e r>? There is no continuous substring "anger" in "manager" The answer should have been <g e r>. What am i missing here?

+12

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

+11

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

+11

//here's my try: https://code.sololearn.com/WdBmmWv0yi79/?ref=app

+10

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

+9

@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

+9

#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

+9

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

+7

https://code.sololearn.com/cXB6Nza1aVUX/?ref=app nice challenge, by the way

+7

I think i found a compact solution with recursion https://code.sololearn.com/czEnKv0fLud1/?ref=app

+6

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

+6

Newbie solution :) https://code.sololearn.com/ckXlQamZzU5P/#cs