Interview Question: Longest Common Substring

24
20



Coding interview question from
In this video, I show how to find the longest common substring between two strings.

Do you have a big interview coming up with Google or Facebook? Do you want to ace your coding interviews once and for all? If so, Byte by Byte has everything that you need to go to get your dream job. We’ve helped thousands of students improve their interviewing and we can help you too.

Stuck on Dynamic Programming? Check out our free ebook: www.dynamicprogrammingbook.com

50 Practice Questions:

You can also find me on
Twitter:
Facebook:
Email: sam@byte-by-byte.com

Nguồn:https://wijstaanvooronzegrondrechten.org/

24 COMMENTS

  1. There is some missing code here (length, most notably) that is included in the website code: https://www.byte-by-byte.com/longestsubstring/

  2. Understand properly and it’s great algorithm and vedio as well. I was thinking how it can be possible with singleArray(n+m) length ?

  3. I get the general idea here, but haven't been able to make this code work. I think the disconnect has to do with the a.substring(i – ?? + 1, i + 1) bit you changed at the end, and I'm sure there's some combination of variables and operators that make it actually work, but haven't been able to work out what those might be yet. I tried the various things mentioned in the video, and various permutations thereof, but haven't figured it out yet. When debugging, it quickly becomes a sea of variables of ABA BABA ABAB A and 1's and 2's and 3's…

  4. for input strings a = "stone", b = "longest" the output would come here as "st" of length 2 which would be wrong. The correct answer would be "one" of length 3. Hence, you should add else case – if a.charAt(i) != b.charAt(j) cache[i][j] = Math.max(cache[i-1][j], cache[i],[j-1])

  5. Good video! But I think it's better to not set the out variable as you go through the matrix. On two large strings, that could waste a lot of time allocating memory.

  6. omg
    this video needs to be remade. The whole time I was confused with the i – length + 1, which is actually i – cache[i][j] + 1.

  7. Sorry to say, I found this tutorial very confusing. For me at least I found the explanation given at https://www.youtube.com/watch?v=BysNXJHzCEs to be much more understandable.

  8. At 13:30 totally agree it’s easier to do 2d array first then optimize to 1d if there’s enough time leftover

  9. Kind of a nitpick here….
    I added a variable: int len = 0;
    Then assigned the value to the cache like so: cache[i][j] = len = cache[i-1][j-1] + 1;

    Here's the nitpick: When I save the current longest String I used: out = a.substring(i – (len-1), i+1);
    I think it makes more sense, and is less confusing than subtracting and then adding back. (i – cache[i][j] + 1)

  10. good video until you changed the substring function at the very end. little more explanation would have helped coz that is the most imp part and a bit confusing as well

  11. When you calculate a.substring(i – length + 1, i + 1), the length is the length of the out string variable, correct?

  12. Your solution produces a Time and Space complexity of 0(nm), is there any particular reason why you chose to create a NxM matrix? I think this can be done in O(1) space?

  13. Hello Sam,

    Thanks for the video series. Just a small request- would it be possible to categorize or tag the problems in types such as DP, Strings, graphs, trees, etc. either on your website or on your YouTube. That will be really helpful.

LEAVE A REPLY

Please enter your comment!
Please enter your name here