[ASSIGNMENT] 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


59 Answers

New Answer




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


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


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


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


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


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


Congratulations for your quiz creation master badge 👍😉


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


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


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?


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


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


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


Here is my try: (taking into consideration contiguous subsequence) https://code.sololearn.com/cDQIvyPz9lJl/?ref=app


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


thanks @tooselfish😊😊


@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


#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


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