Programming Interview Question: Longest Common Substring

Interview question:-
Given two strings S1 and S2, find longest common substrings between them.

For example:-
S1 = "LCLC", S2="CLCL".

LCS = {"LCL", "CLC"}

This video explains the Longest Common Substring Algortihm with the aid of examples and visualization

Source code link:-

[DrStevoXD]

Can be done in O(n + m) time with help of a generalized suffix tree instead of O(n*m) using this DP solution.
Great video tho !

[IDeserve]

Dear Friends,

If you like our content and would like us to continue making great content for you, please spread the word about IDeserve.
A share/appreciation from you on social network would mean the world to us!


Thanks,
-Team IDeserve.

[arpit]

I think its better if you first explain the recursive approach, because that is more easy to understand and gives you the real grasp over then problem. If you understand that one then memoization is the cakewalk.

[md.abdullahalhasan]

Thank you for your efforts .very good explanation.

[AnkitYadav-lfud]

Came to your channel for the first time, watched one video and immediately subscribed.
Thank you for producing such great content.

[edwardkeselman]

Correct me if I am wrong, but in a straight forward solution the number of sub-strings should be O(n^2 - n), because the string is contiguous, however the number of sub-sequences is O(2^n) because it doesn't have to be contiguous.

[vickneshg]

Compare to other are much better keep it up man ☺☺☺☺☺☺

[saturdaynits]

Don't you think this is wrong?

Have a look at :

L C L
C 0 1 1

As per me when we are filling up the last entry (Row 1, Column 3) it means that

we have ;
s1: LCL and
s2: C

so length of common substring between them should be 1 because C is common to both of them.

But as per your table it fills up as 0. Correct me if I misunderstood?

[dspiklu]

Since number of substring is O(n^2) for a string, the complexity should not be O(2^n). (Video at 1:08).

[sachinduhan]

u earned my subscription<3<3 thankx for great explanation

[kuushu]

how it is 2^n, it will be n^4*(string matching time)

[falakk]

Great visual explanation Thank you for your efforts .

Query :: As a naive programmer we can always think of brute force solution, but how do we know that for such solutions we can use matrix based solutions[then calculate diagonally] etc., should we already know hints about how a specific kind of problem e.g. subsequence here, should be solved ? I mean what are your suggestion for a person who is new to problem solving and dont know much tactics .

I hope u got the intuition of question . Thanks .

[shivadamera]

Hello IDeserve Team. I have been exploring all your videos and brushing up my skills. I really appreciate all your effort in making these videos. I am also following your website and its amazing. Code visualization and explanation each and every point is good. Thanks once again to IDeserve team.

secondly, I have one question: in the above video, in the below piece of code

else if (match[i, j] == max)
- max + 1, i));
in the substring it should be i not i+1 as per my understanding. Please correct me if i m wrong.

Thank you

[jvjplus]

whats the recursive solution of it? is there any?

[vishalsaxena]

Please add the annotation (Video at 1:08) the initial solution has complexity O(m*n^2) not O(2^n) as Debankar pointed out

[Saravanakumar-rnfw]

Hi IDeserve, a small correction for you. source code link leads to "Longest Common Subsequence". not to this problem code

[alejandrogarciasalas]

I understand that getting each of substring of a string is O(n^3). Why is comparing each of the substrings O(2^n)? Intuitively it makes sense it grows exponentially but how do you reach that solution?

[jayasree]

Else (in case S1.charAt[i] != S2.charAt[j] ) part should be match[i][j] = Math.Max(match[i-1][j], match[i][j-1]);

[Gurvinder]

DP was meant to be difficult. what did you do sir?

[MrAvtar]

what is complexity of this program with respect to Big O?  is it O(M+N)?
?