5 kyu

Longest Common Subsequence

2,041 of 6,945xDranik
Description
Loading description...
Strings
Algorithms
  • Please sign in or sign up to leave a comment.
  • tobeannouncd Avatar

    Random tests in Haskell could use some work:

    • Almost every pair of random strings contains a longest common subsequence of length 0 or 1, which allows for solutions like this.
    • The error messages for random inputs aren't very helpful:
      • The random strings use characters from the entire range of Char, leading to pairs of strings like "G8\1100651\95058\SUB\\A\b" and "\n\n"
      • When the returned value is shorter than the expected value, the error message will be something like expected: 0 but got: 3, with no indication of what the numbers indicate.
      • When the returned value is not a common subsequence, the error message is expected: True but got: False, which again does not tell the solver what the actual problem is.
  • Extro21 Avatar

    Interesting kata, if only you could add Kotlin :)

  • ahmet_popaj Avatar

    Nice one, quite challenging kata.

  • ryanthestupid Avatar

    'notatest' should equal 'nottest'
    This is wrong, since:
    "A subsequence is different from a substring. The terms of a subsequence need not be consecutive terms of the original sequence."
    Since it does not have to be in consecutive terms, why is a excluded from anothertest and notatest? They both only have one a.

    Correct me if I'm wrong, I'm passing all the other random tests and basic tests, except for this one case.

  • PabloMatMar Avatar

    2/2 A subsequence must be delivered in order. You can say on the instructions that you want it not to be ordered, or it is, or this is and that is not, it is your choice. That you cannot do is require in the test that the string is ordered if it is made up of numbers and not if it is made up of letters without saying anything about this on the instructions...

  • PabloMatMar Avatar

    TWO ISSUES

    1/2 - You must add that although they do not have to be consecutive, they must maintain the direction towards the end of the array, that is, if the first matching term is at index 3 of the longest string, the second cannot be at an index less than 3 ... Your instructions lead to error, non-consecutive does not imply that it must have an address, and you require it in LCD("anothertest", "notatest") ...

  • hexolio Avatar

    This kata allows code that doesn't return the longest subsequence to pass. I noticed this after trying the 4 kyu performance version, which has an extra initial test: lcs("abcdefghijklmnopq", "apcdefghijklmnobq"), which should return "acdefghijklmnoq". My Python solution returns "abq" for that test but still passes this kata. You should add that test (and maybe some other similar ones) to prevent incorrect code from passing.

  • tomatosonic Avatar

    java no random tests, check this solution

  • gaobas Avatar

    This comment has been hidden.

  • amirkeshavarz Avatar

    This comment has been hidden.

  • DefAir Avatar

    Why is there no kata in c++?

  • user1430804 Avatar

    Great kata.. I relly enjoyed this one !

  • Fasdr Avatar

    This comment has been hidden.

  • hmm444 Avatar

    x: anothertest y: notatest My result: notatest exepted: nottest why is the correct anwser is nottest it should be notatest??

  • hiendinhngoc Avatar

    This comment has been hidden.

  • Raxxillion Avatar

    Would really like to try this in C#. Hopefully a beautiful mind could hook a brother up?

  • user9644768 Avatar

    Ruby 3.0 should be enabled.

  • byblix Avatar

    This comment has been hidden.

  • Luckkkky Avatar

    elo if x,y is anothertest , notatest why i get 'aenost' should equal 'nottest' isn't wrong ?

    finaltest zzzfinallyzzz 'afiln' should equal 'final'

    is f - i subsequence or a -f is more logic cuz we sorting it as subsequence of letters (a-z) or numbers(0-9) not making usfull words and final got 0 subsequence of letters

  • arkangel-dev Avatar

    lcs(anothertest, notatest) should return test. But the assert test is expecting 'nottest' in python

  • JoeyKun Avatar

    This comment has been hidden.

  • yattew Avatar

    This comment has been hidden.

  • paulceli Avatar

    I would propose to add a couple hard coded test cases. I managed to pass by luck on the randomly generated but my solution doesn't always returns the optimal solution. Here are a couple :

    eidhacgfb
    gifbcdaeh
    BEST: idh
    MINE: da

    dgafceihb
    adgebichf
    BEST: dgeih
    MINE: aeih

    fbedgicha
    aebchifdg
    BEST: fdg
    MINE: ei

  • snehilk1312 Avatar

    This comment has been hidden.

  • el-iot Avatar

    There's a small mistake in the description section of the python translation of this kata:

    Example subsequence

    Subsequences of "abc" = "a", "b", "c", "ab", "ac", "bc" and "abc".

    "ac" is not a subsequence of "abc" :)

  • dapo_t Avatar

    This comment has been hidden.

  • R4zeel Avatar

    This comment has been hidden.

  • themasterofnone Avatar

    The test is saying that the Longest Common Subsequence of "anothertest" and "notatest" is the substring "nottest". Please explain how this is correct. It makes absolutely no sense.

  • user9240328 Avatar

    This kata might as well just be the link to the wikipedia page and that's it.

    Feels like school :(

  • kidCaulfield Avatar

    So I've solve the Kata! However on submit I was sent to blocked solutions page. I'm wondering whats gone wrong here. Quite possible my solution just sucked horribly and did not deserve the on honor of seeing the solutions. Or is this a bug?

  • ccc997 Avatar

    My appologies if someone has already pointed this out, but I noticed that the tests do not cover cases where two strings are of equal length, many solutions pass because they get "lucky".

    Test.assertEquals(LCS("132535365", "123456789"), "12356") // Test Passed: Value == '12356' Test.assertEquals(LCS("123456789", "132535365"), "12356") // Expected: '12356', instead got: '1356'

  • byczkos Avatar

    I have a problem : expected: not[]test but was:not[a]test I don't know what I am doing wrong :(

  • Mo:lle Avatar

    This comment has been hidden.

  • jamad Avatar

    This comment has been hidden.

  • ivoryblakk Avatar

    You need to add more sample cases. You are wasting people's time by not adding

    Test.assertEquals(LCS("anothertest","notatest") , "nottest);

    Your Kata is just making alot of people frustrated. Having only 2 test shown is lazy.

  • ekaruk Avatar

    I have get in Java version result of test expected: <a[c]> but was:<a[]> Result must be String. What does it mean a[c]? String "a" or "c" ? Correct wrong result usually look like this : expected:<[ab]> but was:<[abc]>

  • ouromoros Avatar

    The tests are REALLY tolerable. I see a couple of quite stupid Haskell solutions. Makes me feel kind of discouraged.

  • jimylja Avatar

    X="anothertest" Y="notatest" Expected: 'nottest', instead got: 'anotetst'. I don't understand. Why the "a" is not included?

  • metalim Avatar

    https://www.codewars.com/kata/reviews/5275754fa4bf4a81f7000304/groups/52fa94ddae9cf038070000ff Apparently tests are not covering longest solution possible. Please add 2 cases: 'bert' == LCS 'berta', 'albert' 'bert' == LCS 'albert', 'berta'

  • marchello Avatar

    getting error: expected:<not[test]> but was:<not[aes]>

    where can I see input parameters values for this sample test?

  • lbvf50mobile Avatar

    This comment has been hidden.

  • mubli Avatar

    This comment has been hidden.

  • cacr Avatar

    Scala translation submitted, can someone have a look ?

  • sanada1615 Avatar

    The tests for submission should show input and output, because it's pretty much impossible to debug without seeing what my function is outputting (I pass all tests accept the last one).

  • DCrow Avatar

    Expected: '12356', instead got: '13256'

    Should pass, since it's the same combination

  • DCrow Avatar

    Test case: "anothertest" "notatest" fails with

    Expected: "nottest", instead got: "anotetst"

    Why? "anothertest" has all of the characters of "notatest". This means any combination of "notatest" characters is correct.

  • LIUTIANZHU@GMAIL.COM Avatar

    IN THE FINAL TEST, THE KATA GIVES:

    anothertest notatest

    AND RESPONCE:

    'test' should equal 'nottest'

    IS 'nottest' A SUB?

    ['n', 'no', 'not', 'nota', 'notat', 'notate', 'notates', 'notatest', 'o', 'ot', 'ota', 'otat', 'otate', 'otates', 'otatest', 't', 'ta', 'tat', 'tate', 'tates', 'tatest', 'a', 'at', 'ate', 'ates', 'atest', 't', 'te', 'tes', 'test', 'e', 'es', 'est', 's', 'st', 't']

  • wthit56 Avatar

    My solution passes, but shouldn't.

    In this other kata there's the test of: abcdefghijklmnopq vs apcdefghijklmnobq, which should be acdefghijklmnoq. That's not what my code produces because it doesn't do a deeper search of skipping certain matches to get a longer subsequence.

  • Blissus Avatar

    I don't understand why this is 4 kyu. Are the test cases so simplistic that I am actually doing something I shouldn't?

  • mxia Avatar

    This comment has been hidden.

  • wthit56 Avatar

    A bit of an ordeal trying to figure out what a "subsequence" is. It's not explained in the description or the wikipedia entry, as far as I can see. I'd recommend explicitly stating that each character of the LCS should be found after the previous character within each string.

  • jpreira Avatar

    .

  • dclaiche Avatar

    This comment has been hidden.

  • mantpaa Avatar

    not should equal "nottest". Woah, what a nice fail statement. Really makes me want to rate this zero.

    Sick of solving katas, only to discover they cannot be beaten due to some bullshit assert statement.

  • pcrama Avatar

    Add test cases to "prevent" solutions like https://www.codewars.com/kata/reviews/5486115fd8325ec04c0001ea/groups/55988c1318b9e971f300001a or https://www.codewars.com/kata/reviews/5486115fd8325ec04c0001ea/groups/57cd9854fa9fc50f580002b7 which do not preserve the order of the input strings.

    E.g. lcs "12345" "45321" == "45"

    Also, a property test could be added to verify that lcs x y == lcs y x

  • chris_m Avatar

    I'm receiving an error that says 'a' should not in the expected results. Doing a console log of the two sequences reveals that it should be included. I'm not sure why or what to do about it. Hope to hear from you soon! :)

  • see1195 Avatar

    This is far too easy for 4 kyu. Very long strings should be added to the tests to avoid solving it by brute force. If you have to use recursion and memoization to first find the lcs length this could be accepted as difficulty 4.

  • haugk Avatar

    Haskell

    Imho this is too easy for 4kyu. Some nice solutions though.

  • Hanni4423 Avatar

    What is the third test case? My function works for all the tests before it, just not that one. It says "Expected: ac, instead got: a".

  • MMMAAANNN Avatar

    As noted by @computerguy103 7 months ago, this kata really needs improvement - it must have more complicated test cases with intermittent subsequences.

    This is critical to improve right now, because this kata will soon reach 500 solutions and then test cases will become permanent.

    Contributors, please add more test cases ASAP!

  • GiacomoSorbi Avatar

    Ruby translation submitted :)

  • Azuaron Avatar

    Python translation complete.

  • computerguy103 Avatar

    It would help if there was another test cases to possibly trap solutions which don't correctly look ahead to find the longest common subsequence.

    Test.assertEquals(LCS("abcdefghijklmnopq", "apcdefghijklmnobq"), "acdefghijklmnoq");
    

    It's possible that some solutions (this one, for instance) would return either "apq" or "abq", depending on which string they're using as the basis to match characters into the other string.

    Also, that appears to be a difficult test case to compute - many of the solutions took around 3-3.5 seconds on my machine, and one took more than 2 minutes. It could be a good test of the solution's efficiency, causing inefficient solutions to time out.

  • Ivan Diachenko Avatar

    This comment has been hidden.

  • steinbachr Avatar

    hi, one of the tests are failing for me (nottest != notatest), the one thing I don't love about this Kata is that I don't even really know where to start when trying to debug that problem as many different combinations can yield the result nottest :\

  • haan Avatar

    Although I understand that the LCS problem could figure on Codewars for completeness sake, the kata itself doesn't introduce any new element to it. This leaves mainly three options:

    1. you know the algorithm and know how to implement it
    2. you know the algorithm/don't know the algorithm but you can use google
    3. you don't know the algorithm, refuse to google, and won't ever find it (because if you knew how to find it, you'd already know LCS)

    I prefer katas where the solution to the problem is not immediately obvious. Calling the problem "LCS" and asking for a straightforward implementation is not very challenging.